Typiler

파라매트릭 서치(Parametric Search)는 바이너리 서치와 매우 유사합니다. 차이점은 최적화 문제를 결정문제로 바꾸어 푸는 것입니다. 원하는 조건을 만족하는 가장 알맞는 값을 특정한 오차범위 이내에서 알고 싶은 경우에 사용을 합니다.

• 바이너리 서치 : 배열에서 중앙값이 가리키는 값이 내가 찾는 값인지가 중요
• 파라매트릭 서치 : 원하는 조건을 만족하는 가장 알맞는 값을 찾는 것

동작과정

1. 데이터를 정렬한다.
2. 범위를 반씩 좁혀간다.
3. S 와 E 가 같을때 까지 진행한다.

시간복잡도

바이너리 서치와 같은 O( log N ) 입니다.

참고사이트

https://www.crocus.co.kr/1000

https://en.wikipedia.org/wiki/Parametric_search

기본코드

'#' 의 개수를 알아내는 문제

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;


class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static char[] arr;
    
    static int parametricSearch(int s, int e){
    	
    	int maxIndex = -1;
    	
    	while(s<=e){
    		int mid = (s+e)/2;
    		char mVal = arr[mid];
    		
    		if (mVal == '#') {
                if (maxIndex < mid) maxIndex = mid;
                s = mid + 1;
            }
            else {
                e = mid - 1;
            }
    	}
    	
    	return maxIndex;
    	
    }
    
    public static void main(String[] args) throws IOException {      
    	
    	String str = "#######___";
   		arr = str.toCharArray();
  		
   		int cnt = parametricSearch(0, arr.length-1) + 1;
    		
   		bw.write(cnt+"\n");
    	
        br.close();
        bw.close();        
    }
}