[C++] 백준 1120 - 문자열

www.acmicpc.net/problem/1120

1120번: 문자열

<풀이>

1. 문자열 A와 B를 입력받는다.

2. 문자열 B와 길이가 같아질 때까지, 문자열 A의 앞이나 뒤에 문자를 추가한다.

3. A, B의 차이값 중 최소를 출력한다.

 

<해법>

1. 두 문자열의 차이가 최소가 되는 방법.

=> 문자열 B에서 문자열 A가 어디에 들어갈지를 결정합니다. 결정한 후, A의 앞이나 뒤에 추가되는 문자는 결국 B와 동일한 문자가 될 것입니다(차이값을 최소로 하기 위해). 따라서, B에서 A가 들어가는 공간과 그 때의 차이값만 계산해서 풀 수 있습니다.

 

#include <iostream>
#include <string>
 
using namespace std;
 
string A, B;
int answer;
 
int main() {
 
    //초기화
    A = "", B = "";
    answer = -1;
 
    //입력
    cin >> A >> B;
 
    for (int i = 0; i <= B.length() - A.length(); i++) {
        
        //B문자열에 하나씩 맞춰보기
        int diffCnt = 0;
        for (int j = 0; j < A.length(); j++) {
            if (A[j] != B[i + j]) {
                diffCnt++;
            }
        }
        
        //최소값 갱신
        if (answer == -1 || diffCnt < answer) {
            answer = diffCnt;
        }
    }
 
    //출력
    cout << answer;
 
    //종료
    return 0;
}

 

구현과 문자열에 대해 알아볼 수 있는 문제였습니다.