[ID: 1120] 문자열

• 문제 - https://www.acmicpc.net/problem/1120

1120번: 문자열

• 풀이

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		String a = st.nextToken();
		String b = st.nextToken();

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

	public static int getMinDiff(String a, String b) {
		if (a.equals(b)) {
			return 0;
		}

		char[] aArr = a.toCharArray();
		char[] bArr = b.toCharArray();
		int ret = 100000;

		for (int i = 0; i <= b.length() - a.length(); i++) {
			int min = 0;
			for (int j = i; j < i + a.length(); j++) {
				if (bArr[j] != aArr[j - i]) {
					min++;
				}
			}
			if (min < ret) {
				ret = min;
			}
		}

		return ret;
	}
}

 

• NOTE
  • 작은 문자열을 큰 문자안에서 비교하면서 다른 문자열의 수가 최소가 되는 값을 구하면 된다.
    • 예
      • adaabc aababbc를 인덱스 0부터 비교하면 다른 문자열은 dac 총 3개
      • 인덱스 1부터 비교하면 다른 문자열은 da 2개
      • 따라서 최소값은 2이다.
  • 추가하는 문자열의 경우 무조건 큰 문자열과 똑같은 값으로 추가할 것이기 때문에 추가하는 값에 대해서 고려할 필요는 없다.