[c/c++] 백준 1120 (Silver 4)

🔨 문제

https://www.acmicpc.net/problem/1120

<요약>
문자열 a,b가 주어졌을 때(a.size() < b.size()) , 이 두 문자열의 차이가 최소가 되도록 구하는 문제!

ex. a= minji, b= jimin이라면 두 문자열의 차이는 4이다.

이 때 조건은 a의 크기를 b의 크기로 메꿔가면서 최소가 되어야 한다.

🔨 해결방법

아이디어는 쉽게 떠올렸지만 나에겐 구현이 막막했다ㅠㅠ

문제에서 a 문자열의 길이가 b 문자열의 길이보다 작거나 같게 주어준다.
그래서 a문자열을 b문자열의 사이즈만큼 움직여서 비교하는 것인데

예를 들어 koder와 topcoder는 _ _ koder _ 이런 식으로 채워가면서 움직이는 것이다. 요리조리 움직여서 두 문자열이 겹치는 것이 적도록 만들면 된다.

하지만 어떻게 요리조리 움직이지!?????
알면 단순하지만 내 머리로는 떠올리기 쉽지 않았다.....

반복문을 b.size()-a.size()만큼 돌려주고 그 안에 이중 반복으로 a.size()만큼 더 돌려주면 된다. 밑에 코드 확인

🔨 코드

#include <iostream>
using namespace std;

int main(){

    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    string a, b;
    cin >> a >> b;    
    int cnt = 0;
    int max = 50;

    for (int i = 0; i <= (b.size() - a.size()); i++) { 	// 이 반복문을 떠올리기가 아주 어려웠다..
        cnt = 0;
        for (int j = 0; j < a.size(); j++) {	
            if (a[j] != b[i + j]) cnt++;
        }
        if (max > cnt) max = cnt;
    }
    cout << max;
    return 0;
 }