본문 바로가기

Dot Algo∙ DS/PS

[BOJ] 백준 16172번 나는 친구가 적다 (Large) (Java)

    #16172 나는 친구가 적다 (Large)

    난이도 : 골드 2

    유형 : 문자열 / kmp

     

    16172번: 나는 친구가 적다 (Large)

    첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 200,000) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가

    www.acmicpc.net

    ▸ 문제

    친구가 적은 성민이는 수업에 결석해도 시험이나 과제에 대한 정보를 제대로 얻을 수 없었다. F 학점을 받을 위기까지 아슬아슬하게 결석일 수를 유지하던 성민이는, 어느 날 갑자기 영문도 모른 채 쪽지시험을 보게 되었다!

    갑작스러운 쪽지 시험으로 마음이 급해진 성민이는 매직아이를 사용해 벼락치기를 하기로 한다.

    성민이가 듣는 과목의 교과서는, 알파벳 소문자(a-z)와 알파벳 대문자(A-Z)로만 이루어져 있다. 성민이가 교과서에서 찾고자 하는 키워드도 역시 알파벳 소문자와 대문자로만 이루어져 있다. 하지만, 성민이에겐 큰 문제가 생겼다. 결석한 날의 수업 내용을 친구에게 빌려 필기를 하던 중, 교과서에 숫자(0-9)를 적어버린 것이다.

    키워드를 찾기 힘들어 패닉에 빠진 성민이는 몇 안 되는 친구인 당신에게 도움을 요청했다. 성민이를 도와, 교과서에서 성민이가 찾고자 하는 키워드의 존재 여부를 알려주자.

     입력

    첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 200,000) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가 주어진다. (1 ≤ |K| ≤ 200,000)

    단, 입력으로 들어오는 키워드 문자열 K의 길이는, 교과서의 문자열 S보다 짧거나 같다.

     출력

    첫 번째 줄에 성민이가 찾고자 하는 키워드가 교과서 내에 존재하면 1, 존재하지 않으면 0을 출력한다.

     

    문제 풀이  

    선형시간으로 두 문자열이 일치하는지 찾으려면 O(S*K) =  최대 400억의 연산이 필요하다. 그래서 kmp 매칭 문자열 알고리즘을 사용하는 것이다.  kmp 알고리즘은 매칭 문자를 찾는 연산 횟수를 줄이기 위해서 반복되는 연산을 줄여나가 매칭 문자열을 빠르게 점프하는 기법이다. 이 알고리즘을 사용하면 O(S+K)의 시간복잡도로 해결이 가능하다. 

     

    해당 문제는 주어진 parent(S)에 숫자를 모두 제거한 후 kmp 알고리즘을 수행해주면 되는 기본적인 kmp 알고리즘 문제이다. 먼저 숫자를 모두 제거하기 위해서는 String 클래스에 있는 replaceAll("[0-9]", "") 메서드를 사용하면 간단히 없앨 수 있다.

     

    부분 일치 테이블 구하기

    kmp 알고리즘에서 가장 중요한 부분은 부분 일치 테이블을 구하는 것이다

    • table[i] = pattern(0...i)의 접두사도 되고 접미사도 되는 문자열의 최대 길이

     

    예를 들어, abacaaba가 있을 때 다음과 같이 구할 수 있다.

     

    i pattern(0...i) 접두사이면서 접미사인 최대 문자열 table[i]
    0    a (없음) 0
    1    ab (없음) 0
    2    aba a 1
    3    abac (없음) 0
    4    abaca a 1
    5    abacaa a 1
    6    abacaab ab 2
    7    abacaaba aba 3

     

    KMP 문자열 매칭 

    부분 일치 테이블로 문자열 매칭을 탐색할 때 점프를 할 수 있어 굉장히 효율적으로 연산을 수행할 수 있다.

    1. parent의 i = 0, pattern의 idx = 0부터 탐색을 시작한다.
    2. if(parent.charAt(i) == pattern.charAt(idx)) 만약 두 문자열이 일치하면 idx를 증가시킨다.
      1. 만약 idx == pattern의 길이와 일치한다면 문자열 매칭이 완료되었으므로 종료한다.
    3. while(idx > 0 && parent.charAt(i) != pattern.charAt(idx))  문자열이 한 글자 이상 매칭된 상태에서 더 이상 글자가 불일치할 경우 현재 대응된 idx를 table[idx-1]로 줄인다.
      1. 이 부분이 중요한데 문자열 매칭이 시작된 후 연속적인 매칭이 이뤄지지 않을 때 다시 매칭을 시작해야하는 시점이다. 다시 매칭을 idx = 0부터 시작하는 것이 아닌 문자열 매칭된 부분이 접두사와 접미사가 일치하는 구간이라면 idx = 0이 아닌 그 일치하는 구간 다음의 idx 값을 받게 된다. 그래서 앞 접두사 부분을 생략하고 빠르게 탐색이 가능해진다.
    static boolean kmp(String parent, String pattern) {
    	int[] table = makeTable(pattern);
    	
    	int n1 = parent.length();
    	int n2 = pattern.length();
    	
    	int idx = 0;
    	for(int i=0; i<n1; i++) {
    		while(idx > 0 && parent.charAt(i) != pattern.charAt(idx)) {
    			idx = table[idx-1];
    		}
    		
    		if(parent.charAt(i) == pattern.charAt(idx)) {
    			if(idx == n2-1) {
    				idx = table[idx];
    				return true;
    			}else {
    				idx++;
    			}
    		}
    	}
    	return false;
    }

     

    KMP 알고리즘에 대해 더 자세히 알고싶다면 여기를 참고해주세요.

     

    풀이 코드 

    import java.io.*;
    
    public class Main {
    
    	public static void main(String[] args) throws IOException{
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		String parent = br.readLine().replaceAll("[0-9]", "");
    		String pattern = br.readLine();
    	
    		System.out.println(kmp(parent, pattern) ? 1 : 0);
    	}
    	
    	static boolean kmp(String parent, String pattern) {
    		int[] table = makeTable(pattern);
    		
    		int n1 = parent.length();
    		int n2 = pattern.length();
    		
    		int idx = 0;
    		for(int i=0; i<n1; i++) {
    			while(idx > 0 && parent.charAt(i) != pattern.charAt(idx)) {
    				idx = table[idx-1];
    			}
    			
    			if(parent.charAt(i) == pattern.charAt(idx)) {
    				if(idx == n2-1) {
    					idx = table[idx];
    					return true;
    				}else {
    					idx++;
    				}
    			}
    		}
    		return false;
    	}
    	
    	static int[] makeTable(String pattern) {
    		int n = pattern.length();
    		int[] table = new int[n];
    		
    		int idx = 0;
    		for(int i=1; i<n; i++) {
    		
    			while(idx > 0 && pattern.charAt(i) != pattern.charAt(idx)) {
    				idx = table[idx-1];
    			}
    			
    			if(pattern.charAt(i) == pattern.charAt(idx)) {
    				idx ++;
    				table[i] = idx;
    			}
    		}
    		
    		return table;
    				
    	}
    }