[백준] 그리디알고리즘 - 1120. 문자열

문제

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

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

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

 

입력

첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

 

출력

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

 

예제 입력1

adaabc aababbc

 

예제 출력1

2

 

생각

A와 B의 길이가 다를 때, 차이를 최소화 하는 방향으로 A의 길이를 B와 같게 하는 게 이 문제의 핵심인 거 같다.

처음에는 두 문자열의 길이 차를 구해 앞이나 뒤에 문자를 넣어서 값을 구하려고 했다. 근데 그냥 A문자를 B문자와의 차이만큼 이동시켜서 풀면되는 문제다.

 

a d a a b c

a a b a b b c

------------

0 1 1 0 0 1 0  => 3

 

   a d a a b c

a a b a b b c

------------

0 0 1 0 1 0 0  => 2 

 

1. 처음에는 배열을 만들어서 인덱스를 증가시키면서 비교해서 같으면 0 다르면 1을 넣어주려고 했다. 

2. 배열 필요 없이 cnt이라는 변수를 써서 다른 문자일때마다 증가시켜줬다.

3. b의 문자열을 비교할때 i+j를 이용해서 j는 두 문자열 길이의 차까지로 for문을 돌렸다. 

4. min값을 어떻게 계산해야할까 했는데, sum이라는 변수를 두고 엄청 큰 수 999999로 초기화해두고 안의 for문이 끝날때마다 min함수를 이용해서 비교하는 것으로 하였다. 

3. 문자열 길이가 같을 때랑 다를 때를 if else문으로 따로 케이스를 두고 생각했는데 마지막에 따로 케이스를 나누어도 되지 않아서 합쳤다. 

 

 

작성한 코드

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

string a, b;
int sum=9999999;

int main(int argc, const char * argv[]) {
    // insert code here...
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> a >> b;

    for(int j=0; j<=b.length()-a.length(); j++){
        int cnt = 0;
        for(int i=0; i<a.size(); i++){
            if(a[i] != b[i+j])
                cnt ++;
        }
        sum = min(cnt, sum);
    }
    cout << sum << "\n";
    
    return 0;
}