이진 탐색으로 문제 해결하기

이진 탐색이란?

이분 탐색이라고도 하며, 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법을 말한다.

예를 들어서 1부터 9까지의 정수가 담겨있는 배열이 있다고 할 때 6을 찾는다고 가정한다면
1. 중간 값 5를 확인 : 5 < 6 이므로 오른쪽 탐색
2. 오른쪽에서 중간 값 8을 확인 : 6 < 8 이므로 왼쪽 탐색
3. 왼쪽에서 중간 값 6을 확인

이처럼 범위의 값들을 절반 씩 확인하기 때문에 시간을 절약할 수 있다.

---

예제 알고리즘에서는 주어진 시간 안에 문제의 난이도와 숙련도를 비교하여 제한 시간 안에 문제를 모두 해결할 수 있는 최소 숙련도를 구해야 하는 문제이다.

프로그래머스 Lev.2 퍼즐 게임 챌린지

• 난이도(diffs)보다 숙련도(level)가 높다면 timeCur만큼의 시간을 소요한다.
• 숙련도보다 난이도가 높다면 난이도 - 숙련도 만큼 문제를 틀린다.
• 이 때 문제를 틀릴 때마다 timeCur + TimePrev만큼의 시간이 소요된다.
• 위의 시간만큼 문제를 틀린 후 timeCur 만큼의 시간을 추가적으로 소요하고 퍼즐을 해결한다.
• 게임의 전체 제한 시간 limit가 정해져있을 때 퍼즐을 해결하기 위한 최소 숙련도는?

이 문제를 해결하기 위해 최소 숙련도인 1부터 문제의 난이도의 최대값의 사이를 이진 탐색을 진행한다.

public class Test_86_PuzzleGameChallenge { // 퍼즐 게임 챌린지
    public int solution(int[] diffs, int[] times, long limit) {
        // 난이도보다 숙련도가 높다면 timeCur만큼의 시간을 소요한다.
        // 숙련도보다 난이도가 높다면 난이도 - 숙련도 만큼 틀린다.
        // 이 때 문제를 틀릴 때마다 timeCur + TimePrev만큼의 시간이 소요된다.
        // 위의 과정을 반복한 후 timeCur 만큼의 시간을 소요하고 퍼즐을 해결한다.
        // 게임의 전체 제한 시간 limit가 정해져있을 때 퍼즐을 해결하기 위한 최소 숙련도는?

        // 문제를 이진 탐색으로 접근
        // 최소 숙련도 1에서부터 문제의 난이도들 중 최대값 사이를 이진 탐색하여 반복한다.

        int answer = 0;
        int left = 1;
        int right = diffs[0];
        for (int diff : diffs) {
            if (diff > right) {
                right = diff;
            }
        }

        while (left <= right) {
            int middle = (left + right) / 2;
            long totalTimes = getTotalTime(diffs, times, middle);

            if (totalTimes <= limit) {
                answer = middle;
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }

        return answer;
    }

    private long getTotalTime(int[] diffs, int[] times, int middle) {
        long totalTime = 0;

        for (int i = 0; i < diffs.length; i++) {
            if (diffs[i] <= middle) {
                totalTime += times[i];
            } else {
                int failedCount = diffs[i] - middle;
                int timePrev = 0;
                if (i == 0) {
                    timePrev = 0;
                } else {
                    timePrev = times[i - 1];
                }
                totalTime += (long) failedCount * (times[i] + timePrev) + times[i];
            }
        }

        return totalTime;
    }
}

중간에 totalTime을 int로 사용하는 바람에 오버플로우가 발생해서 당황했지만 이 코드로 해결이 가능하다.

---

++ 코드가 지저분해보여서 GPT의 도움을 받아보기로했다.

public class Test_86_PuzzleGameChallenge { // 퍼즐 게임 챌린지
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        int left = 1;
        int right = getMax(diffs);

        while (left <= right) {
            int middle = (left + right) / 2;
            long totalTimes = getTotalTime(diffs, times, middle);

            if (totalTimes <= limit) {
                answer = middle;
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }

        return answer;
    }

    private int getMax(int[] arr) {
        int max = arr[0];
        for (int n : arr) {
            if (n > max) max = n;
        }
        return max;
    }

    private long getTotalTime(int[] diffs, int[] times, int middle) {
        long totalTime = 0;

        for (int i = 0; i < diffs.length; i++) {
            if (diffs[i] <= middle) {
                totalTime += times[i];
            } else {
                int failedCount = diffs[i] - middle;
                int timePrev = (i == 0) ? 0 : times[i - 1];
                totalTime += (long) failedCount * (times[i] + timePrev) + times[i];
            }
        }

        return totalTime;
    }
}

최대값 구하는 과정을 메서드로 따로 빼고, 단순한 if문을 3항 연산자로 간단하게 구현했다.

3항 연산자는 엄청 자주썼는데 생각이 안나서 아쉽...