[프로그래머스] 양궁 대회

🔒 문제

문제 링크

🔑 해결 아이디어

전형적인 파라메트릭 서치를 사용하는 문제이다.

Parametric Search란?

parametric search에 대한 사전적 정의 같은 것은 서술하지 않겠다. 조금만 구글링 해 보아도 쉽게 찾을 수 있으니,,, 대신 이후 내가 다시 인사이트를 얻을 수 있도록 parametric search를 사용하는 문제를 판단하고, 사용하는 데 도움이 되도록 활용 면에서 정리를 해 두겠다.

parametric search는 Binary search의 일종이다. 그러나, parametric search는 탐색하는 값이 보통 우리가 구하고자 하는 정답 이라는 점이 다르다.
이번 문제의 경우에도, 각 검사관이 몇명의 사람을 검사하는가? 가 아닌, 총 시간이 얼마나 걸렸는가? 라는 정답을 이진탐색으로 조사하는 방법이다.

Parametric search의 활용

parametric search는 다음의 두 단계로 정리할 수 있다.

1. 탐색 범위 조정
2. 탐색 값 검증

즉, 매 시도마다 정답이 존재할 수 있는 범위를 줄여 나가면서, 값을 검증해 나가는 방식이다.
이를 위해, 값을 검증하는 조건이 중요해 진다. 이번에 우리가 검증하는 값이 우리가 원하는 값인지 확인하는 것이다.

이번 문제의 경우 우리가 확인하는 시간 내에 모든 사람을 검사할 수 있는가? 와 이 시간이 정말 최솟값인가? 의 두가지 조건에 대해 해당 값을 검증해 나가는 것이다.

Parametric search의 사용 조건

parametric search는 다음과 같은 상황에서 사용할 수 있다.

1. 주어진 값으로 정답을 확인할 수 있어야 한다.
2. 탐색하고자 하는 값이 연속된 범위 내에 존재해야 한다.

즉,
1) 우리가 가진 시간을 이용해 해당 시간이 정답 범위 내의 값인지?, 우리가 원하는 값인지? 를 검증할 수 있어야 하며,
2) 이 시간을 탐색하고자 하는 정답 후보 범위는 모두 연속적이여야 한다.

조금 더 팁을 주자면, 1) 주어진 입력의 크기, 또는 탐색해야 하는 경우의 수가 매우 크며, 2) 최솟값, 또는 최댓값을 구하는 문제 에서 자주 사용할 수 있을 것 같다.

💻 소스코드

import java.util.*;

class Solution {
    public long solution(int n, int[] times) {
        //parametric search : 답이 정해져 있다고 보고 전체 답의 범위 내에서 답을 검증해 나가는 방법
        
        long minTime = 0;
        long maxTime = Long.MAX_VALUE;
        
        while(minTime != maxTime){
            long people = n;
            long verifyValue = (minTime + maxTime) / 2;
            //System.out.println(minTime + " " + verifyValue + " " + maxTime);
            for(int i = 0; i<times.length; i++){
                people -= (verifyValue / times[i]);
                if(people <= 0)
                    break;
            }
            if(people <= 0)
                maxTime = verifyValue;
            else{
                if(minTime == maxTime - 1)
                    minTime++;
                else
                    minTime = verifyValue;
            }
        }
        
        return minTime;
    }
    
}