[1120] 문자열

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

1120번: 문자열

 

---

 

🔎 해결 방법

현재 순간에서 가장 최선의 경우만 고려하는 그리디 알고리즘의 특성을 이용하면 생각보다 코드도 짧고 간단한 문제였다.

예를 들어 A = "adaabc", B = "aababbc" 라면

먼저 (B[0], A[0]), (B[1], A[1]), (B[2], A[2]) ... 이런식으로 비교를 한 다음,  다른 경우에만 gap을 증가시켜 주면 된다.

따라서 이 경우에는 A = "adaabcc", gap = 3이 된다.

 

그 다음으로는 (B[1], A[0]), (B[2], A[1]), (B[3], A[2]) ... 이런식으로 비교를 한 다음 마찬가지로 다른 경우에만 gap을 증가시켜 주면 된다.

따라서 이 경우에는 A = "aadaabc", gap = 2가 된다.

 

이렇게 (B의 길이 - A의 길이) 만큼 큰 for문을 돌면서 A[j] 와 B[i + j]의 값을 비교해주면서 gap을 구하고,

그 중 가장 작은 값을 답으로 출력하면 끝!

 

---

 

💡 내 코드(C++)

// [1120] 문자열
// https://www.acmicpc.net/problem/1120
// 그리디 알고리즘, 브루트 포스

#include <iostream>
using namespace std;

int main(void)
{
    string a, b;
    int gap = 0, minGap = 50;
    cin >> a >> b;

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

        if(minGap > gap)
            minGap = gap;
    }

    cout << minGap << endl;
}