[백준] [1120] 문자열

문제

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

예제 입력 1 복사

adaabc aababbc

예제 출력 1 복사

2

예제 입력 2 복사

hello xello

예제 출력 2 복사

1

예제 입력 3 복사

koder topcoder

예제 출력 3 복사

1

예제 입력 4 복사

abc topabcoder

예제 출력 4 복사

0

예제 입력 5 복사

giorgi igroig

예제 출력 5 복사

6

※코드

import java.io.*;
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;
		
		st = new StringTokenizer(br.readLine());
		
		String A = st.nextToken();
		String B = st.nextToken();
		
		int dap = -1;
		for(int i=0;i<B.length()-A.length()+1;i++) {
			int len = 0;
			for(int j=0;j<A.length();j++) {
				if(A.charAt(j) == B.charAt(j+i)) len++;
			}
			if(dap < len) dap = len;
		}
		System.out.println(A.length()-dap);
	}
}

※생각정리

백준 1120번 문자열문제는
문제레벨이 실버4라서 조금 더 복잡한 로직이 필요한 문제라고 생각했었다.
결국은 두문자열을 비교하여 가장긴 공통수열의 길이를 구한 후 더 작은 문자열에서 공통수열의 길이를 빼면 되는 문제였다.

B문자열의 길이 - A문자열의 길이 +1만큼 인덱스를 증가하며 1대 1 비교하면 된다.

※결과

-새벽코딩-