[백준 1120번][Java] 문자열

www.acmicpc.net/problem/1120

1120번: 문자열

 

문제 풀이

 

이 문제의 핵심은 임의로 붙여진 부분은 신경쓸 필요가 없다는 사실을 간파하는 겁니다.

문제에서 초기의 문자열 A가 주어지고 이 문자에 앞,뒤에 임의의 문자를 붙여 B와 길이를 맞춘다고 했습니다.

문자열 간의 다른 부분을 최소화하기로 했으므로 임의로 붙인 문자열은 B에 대응하여 같은 부분이여야 합니다.

 

이 상황을 이해하면 문제가 간단해집니다. 초기 문자열 A가 B의 어느 부분에 위치하던지 나중에 붙인 문자열은  B와 같을 수 밖에 없기 때문에 초기 문자열 A와 차이가 가장 적게 나는 B의 부분만 찾으면 됩니다.

 

import java.io.*;
import java.util.StringTokenizer;

/*
백준 1120번 - 문자열
 */
public class Main {
	public static void main(String[] args) throws IOException {
//		InputReader reader = new InputReader("testcase.txt");
		InputReader reader = new InputReader();
		StringTokenizer st = new StringTokenizer(reader.readLine());
		String a = st.nextToken(); String b = st.nextToken();

		System.out.println(solve(a,b));
	}

	private static int solve(String a, String b) {
		int min = 123456789;
		for (int bi = 0; bi <= b.length() - a.length(); bi++) {
			int diff = 0;
			for (int ai = 0; ai < a.length(); ai++) {
				if(b.charAt(bi+ai) != a.charAt(ai)) {
					diff++;
				}
			}
			min = Math.min(min, diff);
		}
		return min;
	}
}

class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}