백준 1120

2019-06-05

문자열

문제

길이가 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

해설

  • __abc
  • abc__
  • _abc_

총 세가지 경우가 나오게 됩니다.

하지만, 연속적으로 동일한 배열이 있는지 확인하고 그 수를 저장한다음,

배열의 길이 차이 만큼 더해주면 간단하게 풀 수 있습니다.

해답

package baekjoon;

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

public class Problem1120 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		
		String str1 = str.split(" ")[0];
		String str2 = str.split(" ")[1];
	
		int max_same = 0;
		for(int i=0; i<str2.length()-str1.length()+1; i++){
		   String temp_B = str2.substring(i, i+str1.length());
		   int same = 0;
		   for(int j=0; j<temp_B.length(); j++){
		       if(str1.charAt(j) == temp_B.charAt(j))
		           ++same;
		  }
		   if(same > max_same)
		       max_same = same;
		}
		System.out.println(str1.length() - max_same);
		
	}

}