[BF] 1120번 문자열

1120번 문자열

 

https://www.acmicpc.net/problem/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의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

 

예제 입력

adaabc aababbc

 

예제 출력

2

 

해결방법

N 의 조건이 N ≤ 50 이고, 시간복잡도는 O(N) 이므로 모든 경우를 탐색한다

 

처음에 이 문제를 보고 백트래킹으로 모든 알파벳을 넣어봐야하나...?? 라는 생각을 했다

하지만 문제의 조건을 보니 앞, 뒤로 아무 알파벳이나 넣어도 된다

즉, B의 자리수와 일치하는 알파벳을 내가 마음대로 넣을 수 있다는 뜻이었다

따라서 현재 문자열끼리만 비교하여 가장 차이가 최소인 A의 위치만 찾으면 나머지 알파벳을 B와 최대한 일치하도록 할 수 있었다

 

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <algorithm>
#define INF 987654321
using namespace std;

string A,B;
int ans;

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> A >> B;
    
    ans = INF;
    
    for(int i=0; i<=B.size()-A.size(); i++){
        int res = 0;
        
        for(int j=0; j<A.size(); j++){
            if(B[i+j] != A[j]){
                res++;
            }
        }
        ans = min(ans,res);
    }
    
    cout << ans << "\n";
    
    return 0;
}