백준 16172 (나는 친구가 적다(Large))

문제

---

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

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

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

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

 

 

 

 

풀이

---

정규식과 KMP알고리즘을 잘 활용하면 풀 수 있는 문제다.

 

정규식 만으로도 풀수 있지만 시간초과가 뜬다.

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		String note = bufferedReader.readLine();
		String keyword = bufferedReader.readLine();
		
		note = note.replaceAll("[0-9]", "");
		Pattern pattern = Pattern.compile(keyword);
		Matcher match = pattern.matcher(note); 
		boolean isTrue = match.find();
		
		if(isTrue)
			sb.append(1);
		else
			sb.append(0);
		
		System.out.println(sb);
	}
}

위의 코드처럼 정규식의 find 메소드를 이용해서 풀 수 있지만, 시간초과가 난다.

 

그래서 기존에 해당 문자열이 존재하는지 찾을 때 사용했던 KMP알고리즘을 이용하였다.

아래의 링크에서 KMP알고리즘을 확인하면 된다.

conpulake.tistory.com/58?category=853119

백준 1786 (찾기)

<전체코드>

import java.io.*;
import java.util.*;
import java.util.regex.*;

public class Main {	

	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		String note = bufferedReader.readLine();
		String keyword = bufferedReader.readLine();
		
		note = note.replaceAll("[0-9]", "");
		
		int[] pi = new int[keyword.length()];
		
		int j = 0;
		for(int i = 1 ; i < keyword.length() ; i++) {
			
			while(j > 0 && keyword.charAt(i) != keyword.charAt(j)) {
				j = pi[j - 1];
			}
			
			if(keyword.charAt(i) == keyword.charAt(j)) {
				pi[i] = ++j;
			}
		}
		
		j = 0;
		boolean isTrue = false;
		for(int i = 0 ; i < note.length() ; i++) {
			while(j > 0 && keyword.charAt(j) != note.charAt(i)) {
				
				j = pi[j - 1];
			}
			
			if(keyword.charAt(j) == note.charAt(i)) {
				++j;
				if( j == keyword.length()) {
					isTrue = true;
					break;
				}
			}
		}
			
		if(isTrue)
			sb.append(1);
		else
			sb.append(0);
		
		System.out.println(sb);
	}
}