[알고리즘 TIL] 퍼즐 게임 챌린지

문제

https://school.programmers.co.kr/learn/courses/30/lessons/340212

프로그래머스

프로그래머스 LV2. 이진탐색

설명

제한 시간 내에 퍼즐을 풀 수 있는 level의 최솟값는 문제이다. 제한 시간이 10^15 범위를 가지고 있어서, long으로 totalTime 변수 타입을 잡아줘야 한다.

처음에는 단순히 완전 탐색으로 풀었더니 시간 초과가 났다.

static class Solution {
        public int solution(int[] diffs, int[] times, long limit) {
            int level = 1;
            while (true) {
                long totalTime = 0;
                for (int i = 0; i < diffs.length; i++) {
                    if (diffs[i] <= level) totalTime += times[i];
                    else totalTime += ((times[i] + times[i - 1]) * (diffs[i] - level) + times[i] );
                }
                if (totalTime <= limit) break;
                level++;
            }
            return level;
        }
    }

 하지만 이 과정을 통해서 디버깅할 때 조건을 적용하는 방법을 알았다. level 이 294가 나와야하는데 293이 나오는 문제가 생겨서, level==292인 조건에 디버깅을 멈추게 하고 싶었다. 

• level ++; 구문에 breaking point을 건다.
• breaking points 에서 해당 breaking point를 찾아서 condition 을 추가한다. (level == 292)

그 다음부터 디버깅을 더 효율적으로 사용할 수 있겠다.

 

그 다음에는 이분 탐색으로 풀었다. level을 기준으로 start를 1로, end를 300,000으로 두었다. 이때 조건을 충족하는 level은 여러 개가 나올 수 있지만, 그 중 최솟값을 구해야하므로, 반복문을 돌면서 조건을 충족해도 break하지 않고 possibleLevel 리스트에 저장하여 마지막에 그 중 가장 최솟값을 반환한다. 

구현

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    static final List<Integer> possibleLevel = new ArrayList<>();
    
    public int solution(int[] diffs, int[] times, long limit) {
            int start = 1;
            int end = 300000;
            int mid = 0;

            while (true) {
                if (start > end) break;
                mid = (start + end) / 2;

                long totalTime = 0;
                for (int i = 0; i < diffs.length; i++) {
                    if (diffs[i] <= mid) totalTime += times[i];
                    else totalTime += ((times[i] + times[i - 1]) * (diffs[i] - mid) + times[i]);
                }
                if (totalTime > limit) start = mid + 1;
                else {
                    possibleLevel.add(mid);
                    end = mid - 1;
                }
            }
            Collections.sort(possibleLevel);
            return possibleLevel.get(0);
        }
}