문제 푼 날짜 : 2021-09-23

문제

문제 링크 : https://www.acmicpc.net/problem/1120

접근 및 풀이

아래에 문제에 주어진 조건을 보고, 괜히 어렵게 생각해서 구현하는데 시간이 오래걸린 문제였다.

1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.

앞, 뒤로 아무 알파벳을 어떻게 추가해줄까 고민하다가,
생각해보니 어차피 A, B문자열의 차이가 최소가 되게 해야하므로 아무 알파벳이 아니라 차이나는 부분에는 반드시 같은 알파벳을 추가해줘야 할 것이다.
(ex. aab, aabc 가 있다면 당연히 aab의 뒤에 c를 추가해야 차이가 최소가 된다.)

그렇다면 추가해주는 알파벳은 뭘 추가해야할지 고민할 필요가 없이 기존에 주어진 A, B 문자열의 차이의 최솟값만 찾아주면 된다.

문제에 주어진 예제를 통해 위의 설명을 적용해보자면, 문자열 A(adaabc), B(aababbc)가 있을 때, A와 B 문자열 길이 차이만큼 길이가 작은 문자열을 당겨서 비교해줄 수가 있다.
문제에서 A의 길이 <= B의 길이라고 했으므로 굳이 비교할 필요는 없을 것 같다.

Case1.
adaabc
aababbc
-> A기준 인덱스 1(d != a), 2(a != b), 5(c != b) 가 다르므로 3개 차이가 난다.
그러고 나서 마지막에 c를 붙여주면 끝


Case2.
 adaabc
aababbc
-> A기준 인덱스 1(d != b), 3(a != b) 가 다르므로 2개 차이가 난다.
그러고 나서 앞에 a를 붙여주면 끝


즉, 이 두 문자 차이의 최솟값은 2가 된다.

코드

// 백준 1120번 : 문자열
#include <iostream>

using namespace std;

int main() {
    int ans = 987654321;
    string A, B;
    cin >> A >> B;

    int aLen = A.length(), bLen = B.length();

    for (int i = 0; i <= bLen - aLen; i++) {
        int cnt = 0;

        for (int j = 0; j < aLen; j++) {
            if (A[j] != B[j + i]) {
                cnt++;
            }
        }
        ans = min(ans, cnt);
    }
    cout << ans;
    return 0;
}

결과

피드백

쉬워보이는 문제라도 문제의 조건과 입력 케이스를 꼼꼼히 따져보며 구현하자.