(C++) - 백준(BOJ) 1120번 : 문자열

www.acmicpc.net/problem/1120

1120번: 문자열

문자열 비교를 적절히 구현하는 문제였습니다.

 

풀이방법

 테스트 케이스를 통해 설명드리겠습니다.

 a문자열 : adaabc

 b문자열 : aababbc

 일 때 a문자열 앞과 뒤에는 b와 같은 알파벳을 넣는것이 최적의 방법입니다. 따라서 굳이 직접 a문자열의 앞 또는 뒤에 알파벳을 추가한 뒤 비교할 필요가 없습니다. a문자열을 오른쪽으로 한칸씩 옮기며 b문자열과 비교해 차이의 최소만 구하면 답이 됩니다.

 첫 번째 비교는 상기와 같습니다. a문자열의 c알파벳 다음에는 무조건 b의 해당 알파벳과 같다고 가정합니다. 따라서 현재 차이는 두 번째, 세 번째, 여섯 번째 알파벳이 서로 다르므로 3개입니다.

 

 두 번째 비교는 상기와 같습니다. a문자열의 제일 앞 x알파벳은 임의의 알파벳으로 아까와 마찬가지의 가정을 세웠기에 비교 대상에서 제외시킬 수 있습니다. 여기에서 첫 번째인 x를 제외한 뒤 b 문자열과 차이를 구하게 된다면 세 번째, 다섯 번째 알파벳이 서로 다르므로 2개가 됩니다.

 

 이런 방식으로 가장 적은 차이를 구할 수 있습니다.

 

 

Code

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

int main(){
    string a,b;
    cin >> a >> b;
    int ans = 0x3f3f3f3f;
    for(int i = 0; i <= b.size() - a.size(); i++){
        int cnt = 0;
        for(int j = 0; j < a.size(); j++){
            if(a[j] != b[j+i]) cnt++;
        }
        ans = min(ans,cnt);
    }
    cout << ans <<'\n';
}