[백준 1120] 문자열 (C#, C++) - soo:bak

문제 링크

1120번 - 문자열

설명

길이가 더 짧은 문자열 A를, 더 긴 문자열 B에 겹쳐 배치했을 때 두 문자열의 차이를 최소화하는 문제입니다.

여기서 문자열의 차이는 같은 길이일 때 각 위치의 문자가 서로 다른 인덱스 개수를 의미합니다.

문자열 A의 앞이나 뒤에 임의의 문자를 추가하여 길이를 맞출 수 있으므로,

B의 연속된 부분 문자열 중 A와 길이가 같은 구간을 선택해 비교하면 됩니다.

접근법

B 문자열 내에서 길이가 **A문자열과 같은 모든 연속된 부분 문자열**을 추출하여,

해당 문자열과 A문자열을 문자별로 비교합니다.

• 비교 시 두 문자열의 같은 위치에 있는 문자가 다르면 차이를 1씩 증가시킵니다.
• 가능한 모든 배치에 대해 차이를 계산하고, 그 중 최솟값을 선택합니다.

과정은 다음과 같습니다:

1. B의 길이에서 A의 길이를 뺀 만큼 구간을 설정
2. 매 구간마다 A와 B의 해당 부분 문자열을 비교하며 차이를 계산
3. 최소 차이를 갱신해나가며 전체 탐색이 끝난 뒤 정답을 출력

---

Code

C#

using System;

class Program {
  static void Main() {
    var tokens = Console.ReadLine().Split();
    string a = tokens[0], b = tokens[1];
    int minDiff = a.Length;

    for (int i = 0; i <= b.Length - a.Length; i++) {
      int diff = 0;
      for (int j = 0; j < a.Length; j++) {
        if (a[j] != b[i + j]) diff++;
      }
      minDiff = Math.Min(minDiff, diff);
    }

    Console.WriteLine(minDiff);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string a, b; cin >> a >> b;

  int minDiff = a.size();
  for (size_t i = 0; i <= b.size() - a.size(); ++i) {
    int diff = 0;
    for (size_t j = 0; j < a.size(); ++j)
      diff += b[i + j] != a[j];

    minDiff = min(minDiff, diff);
  }

  cout << minDiff << "\n";

  return 0;
}