백준 1120번 문자열

문제 링크입니다: https://www.acmicpc.net/problem/1120

완전 브루트 포스(Brute Force) 알고리즘으로 접근했다가 틀리고 그리디(Greedy) 알고리즘으로 해결한 문제입니다.

알고리즘은 아래와 같습니다.

처음으로 주어진 문자열: s1, 두 번째로 주어진 문자열: s2

1. 결국 s1의 양 끝에 붙이는 알파벳은 s2와 동일하게 붙이면 됩니다.

2. s1은 s2보다 무조건 작거나 같기 때문에 s2의 0 번째 인덱스부터 s1의 시작 지점으로 삼아 같지 않은 인덱스의 수를 셉니다.

3. 2에서 구한 결과 중 가장 작은 값을 출력합니다.

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

 

const int INF = 987654321;

 

string s1, s2;

int result;

 

void minDifference(void)

{

        //greedy하게 접근

        for (int i = 0; i <= s2.length() - s1.length(); i++)

        {

                 int cnt = 0;

                 for (int j = 0; j < s1.length(); j++)

                         if (s1[j] != s2[j + i])

                                 cnt++;

                 result = min(result, cnt);

        }

}

 

int main(void)

{

        cin >> s1 >> s2;

 

        result = INF;

        minDifference();

 

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~