[BaekJoon] 1120 문자열

1.  문제 링크

2.  문제

요약

• 길이가 다른 문자열 A,B가 있는데 B와 길이가 같아질 때까지 A에 앞에 알파벳을 추가하거나 뒤에 알파벳을 추가해서 B와 차이를 최소로 할 때의 차이값을 구합니다. 여기서 차이는 같은 위치에 존재하는 문자의 차이의 개수를 말합니다.
• 입력: 최대 길이가 50이고 알파벳 소문자로만 이루어진 B보다 짧거나 길이가 같은 A와 B가 주어집니다.
• 출력: A를 변형시켜 얻을 수 있는 B와의 차이값의 최솟값을 출력합니다.

3.  소스코드

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

public class Main {
	public int findMinDif(String a, String b) {
		if(a.length() == b.length()) {
			int count = 0;
			for(int i = 0; i < a.length(); i++) {
				if(a.charAt(i) != b.charAt(i)) {
					count++;
				}
			}
			return count;
		}
		int diff = Integer.MAX_VALUE;
		int length_dif = b.length() - a.length() + 1;
		for(int i = 0; i < length_dif; i++) {
			int count = 0;
			for(int j = 0; j < a.length(); j++) {
				if(a.charAt(j) != b.charAt(i + j)) {
					count++;
				}
			}
			if(diff > count) {
				diff = count;
			}
		}
		return diff;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		String a = st.nextToken();
		String b = st.nextToken();
		Main m = new Main();
		System.out.println(m.findMinDif(a, b));
	}
}

4.  접근

• 만약 A의 길이와 B의 길이가 같다면 A에 더이상 변형을 할 수 없으므로 해당 문자열 A와 B의 차이값을 구합니다. 이 차이값이 최솟값이 됩니다.
• 만약 A의 길이가 B의 길이보다 짧다면 현재 B의 문자열에서 A와의 차이값이 가장 적은 곳을 찾습니다.
• 이렇게 하는 이유는 A 중간에 문자를 추가할 수 없고 주어진 A의 앞,뒤에 문자를 추가할 수 있기 때문에 A의 앞과 뒤는 B와 똑같이 맞출 수 있습니다. 그러나 A 중간에 문자를 추가할 수 없어 A 문자열을 B와 똑같이 맞출 수 없고 A 문자열을 그대로 이용해야 하기 때문에 A 문자열과 B 문자열 사이에 가장 차이가 적은 곳을 찾아서 나머지 앞,뒤 부분을 똑같이 맞춘다면 이 때의 차이값이 최솟값이 될 것입니다.
• 위 방법을 이용하여 B 문자열에서 A 문자열과 가장 차이가 적은 곳을 찾아 그 때의 차이값을 출력합니다.