[Baekjoon Online Judge] 1120번: 문자열

1120번: 문자열

요구사항

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

---

전제 조건을 살펴보면, B의 길이는 항상 A보다 길다. 그렇기 때문에 B를 A만큼의 길이로 나누어 비교하여 서로의 차이가 최소가 나야 한다.

 

B: a  a  b  a  b  b  c

A: a  d  a  a  b  c  _  => 같은 문자가 3개이다.

A: _  a  d  a  a  b  c  => 같은 문자가 4개이다.

 

A는 앞 뒤에 아무 알파벳이나 추가할 수 있다. 이때 무조건 B와 같은 자리에 같은 문자를 넣은 경우, 가장 적은 차이를 가져온다. 결국 기존의 A 알파벳에서 같은 문자가 가장 많은 4일 때가 가장 적은 차이를 가져온다. 결국 6 - 4 = 2라는 값을 얻을 수 있다.

 

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

public class Baekjoon1120 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        String[] input = bufferedReader.readLine().split(" ");
        String a = input[0];
        String b = input[1];

        int max = 0;
        for (int i = 0; i <= b.length() - a.length(); i++) {
            String substringB = b.substring(i, i + a.length());
            int sameCount = 0;
            for (int j = 0; j < substringB.length(); j++) 
                if (a.charAt(j) == substringB.charAt(j)) ++sameCount;
            
            if (sameCount > max) max = sameCount;
        }

        System.out.println(a.length() - max);
        bufferedReader.close();
    }
}