[JAVA] 백준 1120 : 문자열

[JAVA] 백준 1120 : 문자열

문제 : 두 문자열 A, B가 주어질 때(A의길이 <= B의 길이), A앞에 아무 알파벳이나 추가하고, A뒤에 아무 알파벳이나 추가하여 B와 길이가 같게 만들어 A[i] B[i]의 차이가 최소인 문자열을 만들고, 그 차이를 출력하는 문제

접근방법

1. 주어진 A를 B와 일치하는 알파벳이 가장 많은 곳에 위치시키고, 나머지를 B와 동일한 알파벳으로 채우면 차이가 최소가 된다.

   예를들어, abc, cbabcaa가 주어질 때

   __abc__ cbabcaa 와 같이 abc를 위치시키면,

   A의 앞뒤를 B와 동일하게 cbabcaa로 만들면 차이가 최소가 된다.

2. A의 앞뒤를 B와 동일하게 만들면 새로 추가한 부분에 대한 차이값은 0이므로, 별도로 고려해주지 않아도 된다.

   즉, A와 B가 가장 많이 일치하는 위치를 찾고, 그 때의 차이값을 출력해주면 된다.

3. B에서 A의 길이만큼의 부분문자열을 얻어와 A와 비교하는 방법을 사용한다.

   String temp_B = B.substring(i, i+A.length());
   int same = 0;
   for(int j=0; j<temp_B.length(); j++){
       if(A.charAt(j) == temp_B.charAt(j))
           ++same;
   }

소스코드

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
String input[] = in.readLine().split(" ");
String A = input[0];
String B = input[1];
​
int max_same = 0;
for(int i=0; i<B.length()-A.length()+1; i++){
    String temp_B = B.substring(i, i+A.length());
    int same = 0;
    for(int j=0; j<temp_B.length(); j++){
        if(A.charAt(j) == temp_B.charAt(j))
            ++same;
    }
    if(same > max_same)
        max_same = same;
}
​
System.out.println(A.length() - max_same);