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

 

---

 

• 코드

실패 코드 : KMP를 써보지 않고 숫자를 모두 제외한 뒤 Contains을 통해 확인해본 결과 시간 초과, KMP 알고리즘을 사용해야지 시간 초과가 나지 않는다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {	
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			
		String firstString = br.readLine();
		String secondString = br.readLine();
		
		for(int i = 0; i < firstString.length(); i++) {
			if(firstString.charAt(i) >= '0' && firstString.charAt(i) <= '9') {
				firstString = firstString.substring(0, i) + firstString.substring(i--+1);
			}
		}
		
		for(int i = 0; i < secondString.length(); i++) {
			if(secondString.charAt(i) >= '0' && secondString.charAt(i) <= '9') {
				secondString = secondString.substring(0, i) + secondString.substring(i--+1);
			}
		}
		
		if(firstString.contains(secondString))
			System.out.println("1");
		else
			System.out.println("0");
	}
}

 

실패 코드 : KMP 알고리즘을 통해서 푼 코드이다. 왜 안되는지 모르겠다.... 계속 메모리 초과가 뜬다...

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Algorithm {	
	static String firstString, secondString;
	static int pi[];
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		firstString = br.readLine();
		secondString = br.readLine();
		pi = new int[secondString.length()];
		
		for(int i = 0; i < firstString.length(); i++) {
			if(firstString.charAt(i) >= '0' && firstString.charAt(i) <= '9') {
				firstString = firstString.substring(0, i) + firstString.substring(i--+1);
			}
		}
		
		System.out.println(KMP());
	}

	// KMP 알고리즘 - pi[] 배열에서 주어진 문자열의 인덱스 0부터 i까지의 부분 문자열 중
	// 접두사 == 접미사가 되는 가장 긴 접두사의 길이를 넣는다.
	// 현재 밑 코드에서 접두사는 j(왼쪽), 접미사는 i(오른쪽)이다.
	static int KMP() {
		// j 접두사
		int j = 0;
		
		// i 접미사
	    for (int i = 1; i < secondString.length(); ++i) {
	        while (j > 0 && secondString.charAt(i) != secondString.charAt(j)) j = pi[j - 1];
	        if (secondString.charAt(i) == secondString.charAt(j)) pi[i] = ++j;
	    }
	    
	    j = 0;
	    for (int i = 0; i < firstString.length(); ++i) {
	        while (j > 0 && firstString.charAt(i) != secondString.charAt(j)) j = pi[j - 1];
	        if (firstString.charAt(i) == secondString.charAt(j)) {
	            if (j == secondString.length() - 1) {
	                return 1;
	            }
	            else ++j;
	        }
	    }
	    return 0;
	}
}

 

 

정답 코드 : KMP 알고리즘을 통해서 푼 코드이다. 앞 선 코드에선 subString으로 숫자를 없애 주는 부분을 KMP 알고리즘에서 숫자를 continue만 해주니까 통과했다..

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {	
	static String firstString, secondString;
	static int pi[];
	
	public static void main(String[] args) throws IOException { 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		firstString = br.readLine();
		secondString = br.readLine();
		pi = new int[secondString.length()];
		
		System.out.println(KMP());
	}

	// KMP 알고리즘 - pi[] 배열에서 주어진 문자열의 인덱스 0부터 i까지의 부분 문자열 중
	// 접두사 == 접미사가 되는 가장 긴 접두사의 길이를 넣는다.
	// 현재 밑 코드에서 접두사는 j(왼쪽), 접미사는 i(오른쪽)이다.
	static int KMP() {
		// j 접두사
		int j = 0;
		
		// i 접미사
	    for (int i = 1; i < secondString.length(); ++i) {
	        while (j > 0 && secondString.charAt(i) != secondString.charAt(j)) j = pi[j - 1];
	        if (secondString.charAt(i) == secondString.charAt(j)) pi[i] = ++j;
	    }
	    
	    j = 0;
	    for (int i = 0; i < firstString.length(); ++i) {
            if(firstString.charAt(i)>='0' && firstString.charAt(i)<='9') continue; // 숫자를 만나면 다음 문자로
	        while (j > 0 && firstString.charAt(i) != secondString.charAt(j)) j = pi[j - 1];
	        if (firstString.charAt(i) == secondString.charAt(j)) {
	            if (j == secondString.length() - 1) {
	                return 1;
	            }
	            else ++j;
	        }
	    }
	    return 0;
	}
}