[Programmers] PCCP 기출문제 2번 / 퍼즐 게임 챌린지 Java

반응형

728x90

[Programmers] PCCP 기출문제 2번 / 퍼즐 게임 챌린지 - LV 2

---

접근

• 이진 탐색

---

풀이

프로그래머스 PCCP 기출문제 2번의 퍼즐 게임 챌린지 문제로 레벨 2의 난이도를 가진 문제이다. 이 문제는 제한 시간 내에 문제를 푸는데 필요한 최소한의 숙련도를 구하는 문제이다.

 

문제를 푸는 기준은 숙련도를 기준으로 결정되며 난이도 - 숙련도의 차만큼 문제 푸는 시간이 증가하게 되는 구조이다. 난이도가 3이고 숙련도가 1일 경우 숙련도가 난이도 보다 2 낮기 때문에 해당 문제를 2번 틀린 후 풀이에 성공하게 된다. 문제를 틀릴 경우 이전 문제를 다시 푼 다음 현재 문제를 풀 수 있어 이전 문제의 풀이 시간이 추가로 소요된다. 이전 문제가 5의 시간을 소요하고 현재 문제가 3의 시간을 소요할 경우 2번 틀린다면 (5 + 3) x 2의 시간이 소요된 후에 현재 문제 풀이에 필요한 시간을 또 소요하여 문제를 푸는 데 성공한다.  총 소요 시간은 (5 + 3) x 2 + 3으로 (이전 문제 소요 시간 + 현재 문제 소요 시간) x 틀린 횟수 + 현재 문제 소요 시간을 총 소요하게 된다. 그리고 문제를 풀고 넘어간 후에 이전 문제 소요 시간으로 접근을 하게 될 경우에는 난이도와 상관없이 1번의 시간으로 풀이가 가능하게 된다. 그나마 다행인 부분은 문제를 틀릴 경우 첫 번째 문제부터 풀어야 하는 게 아니라 바로 전 단계의 문제만 다시 풀면 된다는 것이다.

 

문제를 보고 바로 떠오르는 방법은 당연하게도 낮은 값부터 순차적인 반복을 통해 성공하는 값을 찾는 것이다. 숙련도를 1부터 천천히 올리면서 문제 배열을 순회하며 걸리는 시간을 구한 뒤 제한 시간과 비교를 해 보는 것인데 문제에 주어진 범위들을 보면 문제의 개수가 최대 300,000개, 최고 난이도가 100,000으로 대충 봐도 최악의 경우 3천억 번 정도의 반복을 진행해야 하는 불가능한 방법이다.

 

이번 문제는 어떤 조건을 만족하는 최솟값이나 최댓값을 구하는 문제로 방대한 범위 내에 시간제한을 맞추기 위해선 이진 탐색을 사용해 주어야 한다. 이진 탐색의 경우 시간 복잡도가 log N으로 최악의 경우 log 100,000 = 약 17로 300,000 x 17 = 5,100,000인 3천억에 비해 아주 작은 횟수로 수행이 가능하다.

	int start = 1;
        int end = 100000;
        int answer = 0;

이진 탐색을 위해 범위를 지정하고 시작한다. 문제의 조건으로 난이도, 소요시간, 숙련도 모두 양의 정수를 만족해 1부터 100,000의 범위로 진행하게 된다.

	while (start <= end) {
            int level = (start + end)/2;
            long totalTime = getTotalTime(diffs, times, level);

            if (totalTime <= limit) {
                answer = level;
                end = level - 1;
            } else {
                start = level + 1;
            }
        }

이진 탐색을 수행하는 부분으로 시작점이 끝지점을 넘어가게 되면 반복이 종료된다. 총 소요시간은 정수 범위를 넘어서므로 long을 사용해 주어야 한다. 만약 총 소요시간이 제한 시간보다 작다면 현재 숙련도 값을 저장하고 끝 지점을 현재 숙련도 값 보다 작게 설정하여 앞에 더 작은 값이 존재하는지 탐색하게 된다. 총 소요시간이 제한 시간보다 큰 경우 현재 숙련도가 너무 낮아 실패한 경우로 숙련도를 더 올리기 위해 시작 지점을 현재 숙련도 값 보다 높게 설정하여 탐색한다.

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

        for (int i = 0; i < diffs.length; i++) {
            int solveTimes = diffs[i] - level;

            if (solveTimes <= 0) {
                totalTime += times[i];
                continue;
            }

            if (i == 0) {
                totalTime += (long) times[i] * solveTimes + times[i];
            } else {
                totalTime += (long) (times[i - 1] + times[i]) * solveTimes + times[i];
            }
        }
        return totalTime;
    }

총 소요시간을 구하는 메서드이다. 숙련도와 난이도의 차를 구하여 음수인 경우 현재 문제 난이도 보다 숙련도가 더 높으므로 한 번의 시간 소요로 문제를 풀고 넘어가게 된다. 차가 양수인 경우 이전 문제의 소요시간과 더해져 계산하게 되는데 첫 번째 문제인 경우 이전 문제가 존재하지 않아 현재 문제만 틀린 횟수만큼 시도한 뒤 풀게 된다.

---

전체 코드

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int start = 1;
        int end = 100000;
        int answer = 0;

        while (start <= end) {
            int level = (start + end)/2;
            long totalTime = getTotalTime(diffs, times, level);

            if (totalTime <= limit) {
                answer = level;
                end = level - 1;
            } else {
                start = level + 1;
            }
        }

        return answer;
    }
    
    private long getTotalTime(int[] diffs, int[] times, int level) {
        long totalTime  = 0;

        for (int i = 0; i < diffs.length; i++) {
            int solveTimes = diffs[i] - level;

            if (solveTimes <= 0) {
                totalTime += times[i];
                continue;
            }

            if (i == 0) {
                totalTime += (long) times[i] * solveTimes + times[i];
            } else {
                totalTime += (long) (times[i - 1] + times[i]) * solveTimes + times[i];
            }
        }
        return totalTime;
    }
}

이진 탐색을 떠올릴 수만 있다면 굉장히 쉬운 문제라고 생각한다.