[프로그래머스] 퍼즐 게임 챌린지 level2- JAVA

문제

당신은 순서대로 n개의 퍼즐을 제한 시간 내에 풀어야 하는 퍼즐 게임을 하고 있습니다. 각 퍼즐은 난이도와 소요 시간이 정해져 있습니다. 당신의 숙련도에 따라 퍼즐을 풀 때 틀리는 횟수가 바뀌게 됩니다. 현재 퍼즐의 난이도를 diff, 현재 퍼즐의 소요 시간을 time_cur, 이전 퍼즐의 소요 시간을 time_prev, 당신의 숙련도를 level이라 하면, 게임은 다음과 같이 진행됩니다.

• diff ≤ level이면 퍼즐을 틀리지 않고 time_cur만큼의 시간을 사용하여 해결합니다.
• diff > level이면, 퍼즐을 총 diff - level번 틀립니다. 퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며, 추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다. 이전 퍼즐을 다시 풀 때는 이전 퍼즐의 난이도에 상관없이 틀리지 않습니다. diff - level번 틀린 이후에 다시 퍼즐을 풀면 time_cur만큼의 시간을 사용하여 퍼즐을 해결합니다.

예를 들어 diff = 3, time_cur = 2, time_prev = 4인 경우, level에 따라 퍼즐을 푸는데 걸리는 시간은 다음과 같습니다.

• level = 1이면, 퍼즐을 3 - 1 = 2번 틀립니다. 한 번 틀릴 때마다 2 + 4 = 6의 시간을 사용하고, 다시 퍼즐을 푸는 데 2의 시간을 사용하므로 총 6 × 2 + 2 = 14의 시간을 사용하게 됩니다.
• level = 2이면, 퍼즐을 3 - 2 = 1번 틀리므로, 6 + 2 = 8의 시간을 사용하게 됩니다.
• level ≥ 3이면 퍼즐을 틀리지 않으며, 2의 시간을 사용하게 됩니다.

퍼즐 게임에는 전체 제한 시간 limit가 정해져 있습니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 구하려고 합니다. 난이도, 소요 시간은 모두 양의 정수며, 숙련도도 양의 정수여야 합니다.

퍼즐의 난이도를 순서대로 담은 1차원 정수 배열 diffs, 퍼즐의 소요 시간을 순서대로 담은 1차원 정수 배열 times, 전체 제한 시간 limit이 매개변수로 주어집니다. 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 정수로 return 하도록 solution 함수를 완성해 주세요.

 

접근

적절한 `level`을 찾으면서 한 번 탐색하는 자료의 양이 최대 30만개로 많으니 최대 O(nlog(n)) 시간 복잡도를 가져야겠구나 했다. 그리고 `level`과 걸리는 시간의 연관관계를 따져보니 레벨이 높을수록 시간이 짧아지고, 레벨이 낮을수록 시간이 길어졌다. 이때 `limit`를 넘지 않으면서 최소 레벨을 찾아야 하니 이분탐색으로 풀면 되겠구나 했다.

 

이분탐색의 기준이 되는 값은 level로 두고, 문제대로 총 걸리는 시간을 구해보면서 level을 변경해본다. 주의할 점은 걸리는 시간의 자료형을 long으로 해야한다.

 

그리고 이분탐색에서 제일 어렵다고 생각하는 것이 left, right를 바꿔줄 때 mid를 하냐, mid+1를 하냐 그리고, 답을 left로 하냐 right로 하냐인데 요즘 팁이 생겼다. 사실 멘토님이 알려주신 방법인데 레코드의 수를 엄청 작게하고 몇 번 테스트 해보는 것이다. 그러면 2~3번만 해보면 바로 나온다!

 

코드

import java.util.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        
        int max = 0;
        int min = 1;
        
        // 데이터 저장
        List<Puzzle> ps = new ArrayList();
        for(int i=0; i<diffs.length; i++){
            ps.add(new Puzzle(diffs[i], times[i]));
            
            max = Math.max(max, diffs[i]);
        }

        
        int left = min;
        int right = max;
        
        while(left < right){
            int mid = (left+right)/2;
            // 현재 난이도로 돌려보기
            long sum = 0;
            
            int i;
            int pre = 0;
            for(i=0; i<diffs.length; i++){
                if(sum > limit){
                    break;
                }
                
                Puzzle cur = ps.get(i);
                if(cur.diff <= mid){
                    sum += cur.time;
                }
                else{
                    sum += ((cur.diff - mid)*(cur.time + pre) + cur.time);
                }
                pre = cur.time;
            }
                   
            if(sum > limit){
                left = mid +1;
            }
            else{
                right = mid;
            }
            
        }
        return right;
    }
}

class Puzzle {
    int diff;
    int time;
    
    public Puzzle(int diff, int time){
        this.diff = diff;
        this.time = time;
    }
    

}

 

정렬할 줄 알고 List로 구현한건데 사실 정렬이 필요없어서 배열로 구현하는게 더 낫다. 

 

 

회고

이제 백준말고 프로그래머스에서 연습하려고 레벨 2부터 풀어봤다. 역시 백준이랑 뭔가 다르다. 문제가 더 길고 기업용 코테스럽다. 그래서 풀면서 놓친 점을 되짚어보려고 한다.

 

1. 입출력 예 설명을 대충 봄

문제를 이해하는데 시간이 걸려서 빨리 풀려는 마음에 자세히 나와있는 입출력 예 설명을 안봤다. 그랬더니 계속 답이 아니길래 봤더니 `time_prev` 시간을 틀린 횟수만큼 더해야 하는데 한 번만 더하고 있었다. 

퍼즐을 틀릴 때마다, time_cur만큼의 시간을 사용하며,
추가로 time_prev만큼의 시간을 사용해 이전 퍼즐을 다시 풀고 와야 합니다.

문제를 다시봐도 애매하게 써있어서 입출력 설명을 꼼꼼히 봐야겠다.

 

2. 순서대로 n개의 퍼즐...

이 말이 순서를 골라서 n개를 풀어서 최소값을 만들라는 줄 알고 더 헤맸다. 사실 이 것도 입출력 설명 봤으면 바로 해결될 문제였다. 다음부턴 입출력 예제로 예제 다 이해하고 시작하기!!! 헤매는 시간보다 설명 보는 시간이 훨씬 짧겠다.