[Java]백준 1120 문자열 (그리디문제)

 이 문제는

B문자열을 하나씩 A문자열만큼 돌면서 A문자열과의 차이가 가장 적을 때 그 차이를 출력하면 되는 문제이다.

 

A = aaa

B = bbaaabb

일 때

i = 0 -> aaa, bba -> 2

i = 1 -> aaa, baa -> 1

i = 2 -> aaa, aaa -> 0

. . .

이런 식으로 A문자열과 B의 부분 문자열 가장 차이가 적을 때를 찾으면 된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
// adaabc aababbc
public class b1120_문자열 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String A = st.nextToken();
        String B = st.nextToken();
        
        int ans = A.length();
        
        for(int i=0; i<=B.length()-A.length(); i++) {  // i=0, i=1까지 
            int cnt = 0;
            for(int j=0; j<A.length(); j++) {
                if(A.charAt(j) != B.charAt(i+j)) {
                    cnt++;
                }
            }
            ans = Math.min(ans, cnt);
        }
        
        System.out.println(ans);
    }
}