[프로그래머스][Level3][Java]징검다리 건너기

[문제 설명]

programmers.co.kr/learn/courses/30/lessons/64062

코딩테스트 연습 - 징검다리 건너기

 

[풀이 과정]

파라매트릭 서치(Parametric search)를 이용하여 푸는 문제다. 

단순 코딩으로도 문제를 풀수는 있지만 파라매트릭 서치를 활용하지 않으면 효율성 체크에서 실패가 난다. 

---

 

파라매트릭 서치는 이분탐색과 유사한 알고리즘으로 최적화 문제를 결정 문제로 바꾸어 푸는 것이다. 

 

* 최적화 문제 

- 최적의 해가 무엇인가를 묻는 문제 

- 주로 문제 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제

 

* 결정 문제

- 어떤 조건이 예-아니요로 답이 있는 문제 

 

예시) 최적화 문제 -> 결정 문제 

최적화 문제 : 자동차를 탈 수 있는 사람 중 나이가 가장 어린 사람을 찾아라. 
                    이 때 자동차를 탈 수 잇는 사람은 19세 이상이다. 

 

결정 문제로 변환 : 자동차를 탈 수 있나요? 
                          - 예: 나이가 19세 이상 / 아니요: 나이가 19세 미만 

---

문제에서 구하고자 하는 것은 다음과 같다

"디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는가"

 

최댓값을 구하는 최적화 문제이다.

이 최적화 문제를 나는 다음 질문을 하는 결정문제로 바꿨다. 

"m명은 최대 칸 수 k일 때 건널 수 있는가?"

 

징검다리를 건널 수 있는 최소 인원과 최대 인원은 디딤돌들에 적혀 있는 숫자의 최솟값 최댓값이다.

문제 예시의 디딤돌 최소값은 1, 최대값은 5이다. 

 

최소인원과 최대인원 중간값부터 이분탐색으로 최대 칸 수 k일 때 건널 수 있는지를 체크하면 다음과 같은 틀이 나온다. 

while (min < max) {
    int mid = (min + max + 1) / 2;

    // 조건을 만족하는가
    if (isPossible(mid, k, stones)) {
        // 예
        min = mid;
    } else {
       // 아니요
    max = mid - 1;
}

 

이 때 mid = (min + max)/2 가 아닌 (mid + max + 1)/2로 풀고 있는데, 이 이유는 while문이 무한루프에 빠질 수 있음을 방지하기 위해서다. 자세한 이해는 아래 블로그를 참고했다.

이해를 한 뒤 공식화 하여 외우려 한다. 

 

* 최댓값을 구하는 경우: (min + max + 1) / 2

* 최솟값을 구하는 경우: (min + max) /2

 ialy1595.github.io/post/parametric-search/ 

파라매트릭 서치 (Parametric Search) | ialy's blog

---

[Java code]

package com.algorithm.programmers.level3;

public class Test19 {
    public static void main(String[] args) {

        int[] stones = {2, 4, 5, 3, 2, 1, 4, 2, 5, 1};
        int k = 3;

        System.out.println("answer=" + solution(stones, k));
    }

    public static int solution(int[] stones, int k) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int stone : stones) {
            min = Math.min(min, stone);
            max = Math.max(max, stone);
        }

        while (min < max) {
            int mid = (min + max + 1) / 2;

            // 조건을 만족하는가
            if (isPossible(mid, k, stones)) {
                // 예
                min = mid;
            } else {
                // 아니요
                max = mid - 1;
            }
        }
        return max;
    }

    public static boolean isPossible(int num, int k, int[] stones) {
        int count = 0;
        for (int stone : stones) {
            if (stone - num < 0) {
                count++;
            } else {
                count = 0;
            }

            if (count == k) {
                return false;
            }
        }
        return true;
    }
}