백준 1120 문자열 Java

그리디 문제를 순차적으로 풀다 만난 문자열 문제이다.

알고리즘 분류를 보면 여러 가지 푸는 방법이 있다는 걸 알 수 있는데.

그리디에서 만났기 때문에 그리디스럽게? 풀어보려고 노력했다.

 

처음엔 앞에서부터 비교해보고, 뒤에서부터 비교해보고 더 적게 차이 나는 것에

A문자열의 앞부분이나 뒷부분을 붙이는 방법으로 풀어보려고 했는데

아무리해봐도 실패했다.

 

결론적으로 이 문제는

B문자열을 하나씩 A문자열만큼 돌면서 A문자열과의 차이가 가장 적을 때

그 차이를 출력하면 되는 문제이다.

 

A = aaa

B = bbaaabb

일 때

i = 0 -> aaa, bba -> 2

i = 1 -> aaa, baa -> 1

i = 2 -> aaa, aaa -> 0

. . .

이런 식으로 A문자열과 B의 부분 문자열 가장 차이가 적을 때를 찾으면 된다.

생각해보면 이미 입력받은 A문자열을 수정할 순 없고 앞뒤로 추가만 할 수 있기 때문에

가장 차이가 적은 부분만 찾아서 출력하면 되는 것이었다.

나처럼 멍청하게 앞뒤로 붙여보면서 가장 차이가 적을 때를 는 것이 아니라 말이다.

 

코드는 더더욱 간단하다.

 

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String a = scan.next();
        String b = scan.next();
        int ans = a.length();
        
        for(int i=0; i<=b.length()-a.length(); i++) {
            int cnt = 0;
            for(int j=0; j<a.length(); j++) {
                if(a.charAt(j) != b.charAt(i+j))
                    cnt++;
            }
            ans = Math.min(cnt, ans);
        }
        System.out.println(ans);
    }