[백준] [Silver4] 1120 - 문자열 [Brute Force]

 

---

문제

문자열 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

17063

9473

8235

56.836%

문제

길이가 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의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

예제 입력 1 복사

adaabc aababbc

예제 출력 1 복사

2

예제 입력 2 복사

hello xello

예제 출력 2 복사

1

예제 입력 3 복사

koder topcoder

예제 출력 3 복사

1

예제 입력 4 복사

abc topabcoder

예제 출력 4 복사

0

예제 입력 5 복사

giorgi igroig

예제 출력 5 복사

6

---

풀이

완전탐색이기 때문에 그냥 DFS 방식으로 모든 문자를 앞 뒤로 그리고 a~z까지 다 붙여서 하는 방법이라고 생각할 수 있지만, 그러한 방식의 풀이로는 무한루프 수준의 시간이 걸릴 수 도 있다..

문제를 조금만 다르게 접근하여 해석해보자.

 

중요한 점은 아래의 두 연산이다.

1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.

즉, a~z 중 아무거나 앞 뒤로 넣는것이 일단 가능하다는것이다.

그렇기 때문에 문제는 A가 B와 가장 비슷한 상태로 만들어 놓은 상태에서 1,2 번 연산만 해주면 A와 B의 차이가 최소가 되는 길이가 되는것이다.

그렇다는것은 A와 B가 가장 비슷한 상태의 차이점이 곧 우리가 찾고자 하는 결과값이 된다.

그 이후는 1, 2번 연산으로 어떻게든 맞출 수 있다고 했으니까 말이다.

그러므로 

B 문자열에서 몇번째 인덱스에 A 문자열을 넣었을때 가장 차이가 적은지를 찾으면 된다.

 

즉,

만약 

A : abc

B : fffabczzz

 

라면

 

A가 B의 3번 인덱스에 위치하고 앞에 fff 뒤에 zzz 만 붙여주면 A는 B와 최소의 차이를 나타내는 문자열이 될 수 있다.

그러므로 위에 예에서의 답은 0이다.

 

---

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B1120_문자열 {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String[] inputs = bf.readLine().split(" ");

        String A = inputs[0];
        String B = inputs[1];
        
        int minDiff = Integer.MAX_VALUE;
        int limit = B.length() - A.length();
        for(int i=0;i <= limit;i++){
            int tempDiff=0;

            for(int j=0;j<A.length();j++){
                if(A.charAt(j)!=B.charAt(j+i)){
                    tempDiff++;
                }
            }
            if(minDiff > tempDiff){
                minDiff = tempDiff;
            }
        }
        System.out.println(minDiff);
    }
}