[백준OJ] 1120번 문자열

https://www.acmicpc.net/problem/1120

1120번: 문자열

---

 

풀이

A문자열을 B문자열과 겹쳐가면서 문제를 해결하면된다.

예를들어서 A=adaabc , B=aababbc라고 해보자.

 

먼저 A의 첫번째 문자를 B의 첫번째 문자와 겹쳐본다.

A	a	d	a	a	b	c
B	a	a	b	a	b	b	c

그럼 A의 맨 마지막에는 빈칸이 되는데, 길이를 맞추기위해 아무 알파벳이나 추가해도 된다했으므로, A와B의 길이를 최소로 하기위해서는 해당 인덱스의 원소(c)를 넣어주면 된다.. 

A	a	d	a	a	b	c	c
B	a	a	b	a	b	b	c

이때의 차이는 3이된다.

 

다음으로 A의 첫번째 문자를 B의 두번째 문자와 겹쳐본다.

A		a	d	a	a	b	c
B	a	a	b	a	b	b	c

위와 마찬가지로 차이를 최소로 하기위해 맨 앞에 a를 추가한다.

A	a	a	d	a	a	b	c
B	a	a	b	a	b	b	c

이때의 차이는 2가 된다. 따라서 최소는 2가 된다.

 

문제를 풀때 A문자열을 움직여가면서, 빈공간들은 B문자열의 해당 인덱스의 문자와 같은 문자로 채워준다는 가정하에 A문자열의 길이만큼 탐색하며 B와 비교를 하면 된다.

 

시간복잡도

A와 B의 길이가 최대 50이므로, O((len(b)-len(a))*len(a)) = O(1)이 된다.

 

코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        String a,b;
        int ret=51,gap;
        Scanner scanner = new Scanner(System.in);
        a=scanner.next();
        b=scanner.next();
        for(int i=0;i<=b.length()-a.length();i++){
            gap=0;
            for(int j=0;j<a.length();j++){
                if(a.charAt(j)!=b.charAt(i+j)){
                   gap++;
                }
            }
            ret=Math.min(ret,gap);
        }
        System.out.println(ret);
    }
}