[Baekjoon] 1120_문자열

Silver IV

문제(출처: https://www.acmicpc.net/problem/1120)

---

< 문자열 >

 

문제 풀이 

 

A의 앞 또는 뒤에 아무 알파벳이나 추가할 수 있으므로 어떤 알파벳을 추가할지는 고려하지 않아도 된다. A와 B의 차이를 최소로 만드는 것이 목표이므로 B와 일치하는 알파벳을 넣는다고 가정한다. 차이를 최소로 만들기 위해 고려할 것은 앞과 뒤에 추가할 개수이다. 그러므로 가능한 모든 경우를 확인해 본다. 

 

만약 A와 B의 길이 차이가 3이라면 (앞, 뒤) 순으로 (3,0), (2,1), (1,2), (0,3)를 추가하는 경우를 확인해 본다.

 

 my solution (Java)

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

public class _1120_ { // 문자열
	static String A, B;

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

		A = st.nextToken();
		B = st.nextToken();

		int d = B.length() - A.length();

		int result = B.length();
		if (d == 0) {
			result = Math.min(result, diff(0));
		} else {
			while (d >= 0) {
				result = Math.min(result, diff(d--));
			}
		}

		System.out.println(result);
	}

	private static int diff(int left) {
		int answer = 0;
		for (int i = left; i < left + A.length(); i++) {
			if (A.charAt(i - left) != B.charAt(i)) {
				answer += 1;
			}
		}
		return answer;
	}
}

변수)
A, B : 문자열
d : A와 B의 길이 차
result : A와 B의 차이 최소

 

A와 B의 문자열을 입력받는다. A와 B의 길이 차이를 구한 후 길이 차이가 0이라면 A와 B의 차이 개수를 구한다. 길이 차이가 0이 아니라면 앞과 뒤에 추가할 수 있는 모든 경우의 수를 구한 후 diff 함수를 호출한다. diff의 반환 값을 통해 A와 B의 최소 차이를 구해 출력한다. 

 

diff(int left)

왼쪽에 몇 개를 추가할 것인지 매개변수로 받는다. 왼쪽에 추가한 개수만큼 B와 일치한다고 가정하고 그 후부터 A와 B를 비교해 차이 개수를 구한다.

---

 

---