[BOJ 1120 // C++] 문자열

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1120번 문제인 문자열이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1120

1120번: 문자열

이 문제는 짧은 문자열의 앞과 뒤에 문자를 추가하여 긴 문자열과 길이를 같게 할 때, 두 문자열이 얼마나 덜 차이나게 할 수 있는지를 묻고 있다.

 

한편, 간단히 생각해보면, 짧은 문자열의 위치를 "긴 문자열과 가장 많이 일치하는 곳"에 놓고, 앞뒤로 긴 문자열과 동일하게 문자를 추가하는 것이 두 문자열이 가장 덜 차이나게 하는 방법이라는 것을 알 수 있다.

 

따라서, 문제에서 주어진 문자열의 길이가 작으므로, 반복문을 돌면서 두 문자열을 가장 많이 일치시킬 수 있는 위치를 찾으면 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다. 코드를 읽는다면, 문제에는 짧은 문자열을 X, 긴 문자열을 Y라고 부르고 있으나 코드에서는 X와 Y를 각각 A와 B로 작성했다는 점을 유의하여 읽자.

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string A, B; cin >> A >> B;
    int Alen = (int)A.length(), Blen = (int)B.length();
    int maxmatching = 0;
    for (int i = 0;i <= Blen - Alen; i++) {
        int cnt = 0;
        for (int j = 0;j < Alen;j++) {
            if (A[j] == B[i + j]) cnt++;
        }

        maxmatching = max(maxmatching, cnt);
    }

    cout << Alen - maxmatching;
}