#백준_1120 문자열 - Java 자바

#유형 : 시뮬레이션, 그리디

# 맨 처음에는 DFS 방식으로 접근했으나 메모리 초과. 결국은 그리디 방법으로 해결하였다. 

# 양 끝에 붙이는 알파벳은 Y의 양끝과 동일하게 맞추는게 최소값을 구할 수 있는 방법인것같다. X와 Y의 길이 차이를 구하고, 그 차이 만큼 반복문을 돌리며 X,Y 문자를 비교하며 가장 차이가 적을때의 값을 출력하면 된다.

 

예를 들어 adaabc / aababbc 일 때 아래와 같이 나타낼 수 있고,  아래의 경우에 X에 a를 붙이면 최솟값이라는 것을 확인할 수 있다.

X	a	d	a	a	b	c
Y	a	a	b	a	b	b

 

X	a	d	a	a	b	c
Y	a	b	a	b	b	c

 

 

 

package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p1120 {
    static String X,Y;
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        X = st.nextToken();
        Y = st.nextToken();
 
        int rs = getDiff(X, Y);
        System.out.println(rs);
        
    }
    public static int getDiff(String x, String y) {
        int min = 99999;
        for(int i=0; i<=y.length()-x.length(); i++) {
            int cnt=0;
            for(int j=0; j<x.length(); j++) {
                if(x.charAt(j) != y.charAt(j+i)) {
                    cnt++;
                }
            }
            min = Math.min(min, cnt);
        }
        return min;
    }
}