[백준] 1515 수 이어 쓰기 - 파라매트릭 서치(Paramatric Search) + 부분 수열(SubSequence) JAVA

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

코드설명

파라매트릭 서치 와 부분집합 개념을 활용한 문제입니다.

 

먼저, 부분집합(Subset)은 1부터 N까지의 숫자를 먼저 제가 임의로 만들고, 파라매트릭 서치를 활용하여서 지워진 수가 제가 만든 임의의 수에 부분집합(Subset)인지 확인하고, 최소값을 찾기 위해 최적의 N값을 찾아나갑니다.

 

문제에서 어려웠던점은, 이 문제가 파라매트릭 서치문제인지와 부분집합을 활용해야하는가에 대해 그 자체를 떠올리는 것이 어려웠습니다.

 

또, 문제에 최대 3000자의 input 문자열 값이 주어지는데, 이는 지워진 값으로 원래 N값은 그보다 훨씬 큽니다. 저는 10^6 으로 최대값을 두고 해결했습니다.

코드

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

public class Main {
    public static int N, L;
    public static int[] arr;
    public static int answer = 0;
    public static String input;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
        
		input = st.nextToken();
		answer = paramatric(0, 100000);
		System.out.println(answer);
	}
    
    public static int paramatric(int lo, int hi) {
    	int left = lo - 1;
    	int right = hi + 1;
    	
    	while(left + 1 < right) {
    		int mid = (left + right) / 2;
    		
    		//만약 일치한다면, N값을 줄여본다.
    		if( checkSubSet(input, generateOneToN(mid)) == true) {
    			right = mid;
    		}else {
    			left = mid;
    		}
    		
    	}
    	return right;
    }
    
    public static StringBuilder generateOneToN(int N) {
    	StringBuilder sb = new StringBuilder();
    	for(int i=1; i<=N; i++) {
    		sb.append(i);
    	}
    	return sb;
    }
    
    public static boolean checkSubSet(String inputStr, StringBuilder b) {
    	int i = 0, j = 0;
    	while(i < inputStr.length() && j < b.length()) {
    		if(inputStr.charAt(i) == b.charAt(j)) {
    			i++;
    		}
    		j++;
    	}
    	return i == inputStr.length();
    }
    
    
}