백준 1120 - 문자열

www.acmicpc.net/problem/1120

간단한 문자열 문제

 

처음엔 그냥 앞뒤로 붙여봐서 비교하면 되지 않나?? 했는데 보기좋게 틀렸다 ㅎㅎ

앞, 뒤로 번갈아 붙일 수 있기 때문에 앞뒤로 여러문자가 붙는 상황을 고려해야한다...

예제가 아니더라도 acc xyzabcxyz 가 있다고 가정해보자, 그러면 앞뒤로 xyz가 붙어야 답이 1이 나온다.

 

풀이한 방법은 어차피 앞 뒤로 붙는 문자는 같을것일거고, acc가 가장 적은 차이가 나오는 위치를 찾으면 된다.

문자를 붙일 것 없이 2중for문으로 작은차이가 발생하는곳을 찾자.

 

 

import java.util.*;
public class B1120 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);        
        StringBuilder A = new StringBuilder(sc.next());       
        StringBuilder B = new StringBuilder(sc.next());        
        int aLen = A.length();
        int bLen = B.length();        
        int min = bLen;
        for(int i=0; i<=bLen-aLen ; i++) {
            int cnt = 0;
            for(int j=i ; j<i+aLen ; j++) {
                char a = A.charAt(j-i);
                char b = B.charAt(j);
                if(a!=b) cnt++;
            }
            if(cnt < min) {
                min = cnt;
            }
        }
        System.out.println(min);
        // System.out.println(startIdx);
 
    }
}