/ BOJ

BOJ_1120_문자열_JAVA

문제 : 문자열

링크 : BOJ_1120_문자열

접근 방식

언뜻 보기에 양 옆으로 문자를 추가해가며 값을 비교해야하는 복잡한 문제라고 생각할 수 있지만, 조금만 뜯어보면 그렇게 복잡한 문제는 아니다.

A는 B보다 길이가 작거나 같다. 그리고 A의 양 옆에 알파벳을 추가하여 B와 최대한 같은 문자의 수의 개수를 늘리려고 한다.

이는 B에서 A의 위치를 바꿔가며 B와 가장 공통부분이 많은 위치가 같은 문자의 수를 최대로 하는 위치가 되는 것이다. 나머지 부분은 B와 같은 문자로 채워넣을테니 말이다.

문제는 다른 문자의 개수를 출력해야 하므로, A의 위치를 B의 시작점부터 돌려가며 서로 다른 문자의 개수의 최솟값을 구해서 출력하면 된다.

소스 코드

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

public class BOJ_1120_문자열 {

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

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

		StringTokenizer st = new StringTokenizer(in.readLine());

		char[] A = st.nextToken().toCharArray();
		char[] B = st.nextToken().toCharArray();

		int N = B.length - A.length;
		int answer = Integer.MAX_VALUE;

		for (int i = 0; i <= N; i++) {
			int cnt = 0;
			for (int j = 0; j < A.length; j++) {
				if (A[j] != B[j + i]) {
					cnt++;
				}
			}
			answer = Math.min(answer, cnt);
		}

		System.out.println(answer);
	}

}