BOJ 1120 - 문자열 / C++

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

1120번: 문자열

 

 

문제 풀이

문자열 a와 b를 입력받아 두 문자열의 차이가 최소일 때, 그 차이의 수를 출력하면 되는 문제이다.

이 때, a.size() <= b.size()이고, 문자열 a 앞 또는 뒤에 어떤 알파벳을 추가할 수 있다.

 

문자열 a = "abc", b = "dzwabqwec"라 해보자.

a.size() == 3이고 b.size() == 9이므로 a에는 6개의 문자를 추가하여

abcxxxxxx, xabcxxxxx, xxabcxxxx, ... 등을 만들 수 있다.

 

여기서 알 수 있는 사실은 문자를 실제로 추가할 필요없이
b를 a의 크기만큼 substr하여 비교하는 것이 정답이 된다는 사실이다.

앞선 예제에서는 abc와 dzw를, abc와 zwa를 비교해나가다보면 abc와 abq를 비교했을 때 차이가 최소가 되고

그 값을 출력하면 된다.

소스 코드

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

int diffCharCount(string a, string b) {
    int ret = 0;

    for(int i=0; i<a.size(); i++){
        if(a[i] != b[i]) ret++;
    }

    return ret;
}


int main() {
    string a, b;
    cin >> a >> b;

    int diffSize = b.size() - a.size();

    if(diffSize == 0){
        cout << diffCharCount(a, b);
    }
    else {
        int ans = 100;

        for(int i=0; i<diffSize + 1; i++){

            ans = min(ans, diffCharCount(a, b.substr(i, a.size())));
        }

        cout << ans;
    }
}