백준 1120번 문자열 문제

최근 알고리즘 연습을 하고 있다. 아직 제대로 공부한 것이 아니라 손풀기 용도로 간단한 구현과 문자열 문제만 풀고 있었는데, 조금은 생각해볼만한 문제가 나와서 정리해본다.

적힌 예시로는 잘 알 수 없어 입력 예시를 살펴보니

adaabc aababbc

의 예시가 있었는데, 위의 설명대로 생각해보면 첫번째 문자에 a+adaabc를 하면 두 문자열의 길이가 같아지고 2번, 4번 인덱스의 d와 a가 서로 달라 차이가 2가 된다.

설명대로 A의 앞뒤의 아무 알파벳이나 추가하는 대로 따라가다보면 어떤 알파벳을 추가해야하는지 결정해야하는데, 무작정 B의 앞뒤에 있는 걸 추가하자니 너무 많은 예외가 등장한다.
예를 들어,
abcabdabc abcabcabcc 라고 되어있으면 앞뒤에 어떤 문자를 추가해야할까. 뒤에 c를 붙이면 해결될 것 같지만 이런 경우 모든 경우를 생각해 조건문으로 달아줘야해서 빗나가는 예외가 발생할 가능성이 매우매우매우 농후하다.

잘 생각해보면 A의 길이 <= B의 길이이므로 A의 길이만큼만 검사하면 될 것이다. B에서도 A의 길이만큼만 검사해서 일치하지 않는 문자를 세어준다. 단, 앞뒤에 문자를 추가할 수 있으므로 B에서 검사하는 구간을 반복마다 이동시켜준다.
예를 들어,

A : abcd
B : xyabcdxy 이면,
abcdOOOO
OabcdOOO
OOabcdOO
OOOabcdO
OOOOabcd (O는 추가한 미지의 알파벳)

실제로 알파벳을 추가하는 것이 아니라 어차피 추가한다면 B와 최대한 일치하게 알파벳을 추가할테니,
추가했다고 가정하고 검사를 진행하자는 아이디어이다.

        int diff = A.length();
        for (int i = 0; i <= B.length() - A.length(); i++) {
            int k = 0;
            for (int j = 0; j < A.length(); j++) {
                if (A.charAt(j) != B.charAt(i + j)) {
                    k++;
                }
            }
            if(diff > k) {
                diff = k;
            }
        }

코드는 단 몇줄로 끝난다.