[1120번] 문자열

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 단순한 생각

2. brute force

앞으로 넣거나 뒤로 넣어도 된다고 하여 deque를 이용한다, 스택, 큐를 이용한다는 그런 생각보다는

일단 이 문제의 최대 범위를 확인해보면 50밖에 안되니 그냥 brute force로 해결 할 수 있는 문제이다.

괜히 더 생각을 깊게하면 꼬이게 되고, 자칫하면 brute force보다 더 안좋은 결과를 초래할 수 있다.

이 코드는 

A : abcd

B : abcdefg 면

A :  abcd

B : abcdefg 

A :    abcd

B : abcdefg 

A :     abcd

B : abcdefg 

이런식으로 비교하는 알고리즘이다.

소스 코드 : 

#include <iostream>
#include <string>
 
#define INF 9999
 
using namespace std;
 
int main()
{
    int d, min = INF;
    int lenA, lenB;
    
    string a, b;
 
    cin >> a >> b;
 
    lenA = a.length();
    lenB = b.length();
    
    for (int i = 0; i <= lenB - lenA; i++)
    {
        d = 0;
        for (int j = 0; j < lenA; j++)
            a[j] != b[i + j] ? d++ : 0;
 
        if (min > d)
            min = d;
    }
    cout << min;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>