🎈 문제 풀이

그리디 알고리즘 + 정렬 문제의 전형입니다.

문제에서 발판을 선택하는 순서는 boxes 에 나타난 순서를 따르지 않아도 되기 때문에 boxes 배열을 오름차순으로 정렬하여 생각해도 무방합니다.

문제 상황 속에서 찾을 수 있는 가장 큰 힌트는,
각 순간마다 올라갈 수 있는 가장 높은 상자로 올라가는 전략이 선택하는 발판의 개수를 최소화한다는 점입니다.

그 이유는 현재 높이 h인 벽을 넘을 수 없는 상태에서

올라갈 수 있는 상자 $b_1$, $b_2$ 가 있고 $b_1 < b_2$를 만족한다면

$b_1$으로 올라가는 것은 $b_2$로 올라가는 것 보다 다음에 선택할 수 있는 상자의 후보를 감소시켜 항상 손해인 선택이 되기 때문입니다.

이와 같이 각 순간에 현재의 이득을 최대화하도록 행동하는 것이 결과적으로 전체의 최대 이득을 가져오는 알고리즘 접근법을 그리디 알고리즘이라고 합니다.

위에서 설명한 전략을 의사 코드로 간단하게 작성하면 아래와 같습니다.

curr_height = 0; answer = 0;
while (curr_height가 h를 뛰어 넘기에 부족함) {
	t = 남은 상자들 중에서 올라갈 수 있는 최대 높이; 
	curr_height = t;
	answer += 1;
}
return answer;

남은 상자들 중에서 올라갈 수 있는 최대 높이를 구하는 것은 크게 두 가지 방법으로 구현할 수 있습니다.

1) 이분탐색(Binary Search)를 수행하거나,
2) 단순히 반복문으로 상자들을 순회하면서 한도 내에 드는 가장 높은 상자를 찾는 것입니다.

1. 이분탐색(Binary Search)

이분탐색은 어떤 정렬된 배열에서 특정 값 이상/이하가 되는 경계를 찾는데 유용하게 이용될 수 있는 알고리즘입니다. Java에서는 Arrays.binarySearch와 같은 검증된 표준 라이브러리 함수를 사용할 수 있기 때문에 표준 라이브러리의 도움으로 보다 쉽게 구현할 수 있습니다.
Java의 Arrays.binarySearch 는 배열에서 특정 값이 존재하는 인덱스를 찾아주거나, 그 값이 존재하지 않는다면 처음으로 그 값보다 큰 원소가 등장하는 인덱스를 찾아줍니다.

현재 높이에서 정확히 k 만큼 높은 위치가 존재한다면 그 상자로 이동하는 것이 가장 좋을 것이고,

현재 높이 + k 보다 높은 위치를 찾았다면 그 위치 이전의 상자는 이동할 수 있는 상자였을 것이므로

그 이전의 상자로 이동하는 것이 최선입니다.
(단, Java의 Arrays.binarySearch 는 배열에 찾으려는 값이 여러 개 있을 경우 그것들 중 무엇을 찾아주는지 명시되어있지 않기 때문에 중복된 값을 허용하는 문제상황에서는 조심해야 합니다.)

1. 반복문 순회

이동할 수 있는 가장 높은 상자를 찾는 것에 단순한 반복문을 이용할 수도 있습니다.
상자 배열이 정렬되어있고, 이미 순회한 상자는 다시 순회할 일이 없기 때문에 효율적인 선형 시간복잡도 알고리즘을 작성할 수 있기 때문입니다. 그러나 구현 과정 중 많은 조건 분 기가 포함될 수 있어 코드를 작성하는 시간은 이분탐색을 이용하는 시간보다 오래 걸릴 수 있습니다.

import java.util.Arrays;

public class Solution {
    public int solution(int h, int k, int[] boxes) {
        Arrays.sort(boxes);

        int selected = 0, currIndex = -1, currHeight = 0;
        while (currHeight + k < h) {
            // 남은 상자들 중에서 높이가 target 이하인 위치들 중
            // 가장 인덱스가 큰 위치를 찾아야 합니다.
            // 이를 위해 binary search를 통해 높이가 currHeight + k 이상이 되는
            // 첫 지점을 찾습니다.
            int pos = Arrays.binarySearch(boxes, currIndex + 1, boxes.length, currHeight + k);
            if (pos >= 0) {
                // 반환값이 양수라면,
                // 높이가 현재 높이보다 정확히 k만큼 큰 상자를 찾은 것.
                selected++;
                currIndex = pos;
                currHeight = boxes[currIndex];
            } else {
                // 반환값이 음수라면,
                // 이 값은 (- "currHeight+k보다 큰 값이 처음으로 등장하는 인덱스" - 1)
                int gtIdx = -(pos+1);
                if (gtIdx == currIndex+1) {
                    // 더 이상 올라갈 수 있는 상자가 없음.
                    return -1;
                } else {
                    // gtIdx-1 위치의 상자는
                    // 현재 위치에서 올라갈 수 있는 가장 높은 상자.
                    selected++;
                    currIndex = gtIdx-1;
                    currHeight = boxes[currIndex];
                }
            }
        }
        
        return selected;
    }
}