[프로그래머스] 퍼즐 게임 챌린지 (Java)

0. 출처

프로그래머스 퍼즐 게임 챌린지 문제입니다.

1. 문제

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

 

- diff <= level 이면 퍼즐을 틀리지 않고 time_cur 만큼의 시간을 사용하여 해결합니다.

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

 

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

(1) 입력

퍼즐의 난이도를 순서대로 담은 1차원 정수 배열 diffs, 퍼즐의 소요 시간을 순서대로 담은 1차원 정수 배열 times, 전체 제한 시간 limit이 매개변수로 주어집니다.

(2) 출력

제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값을 정수로 return하도록 solution 함수를 완성해 주세요.

2. 문제 풀이

(1) 문제 풀이 방법

처음에는 단순히 diffs 중 MAX 값부터 시작해서 값을 줄여나가면서 검사하면 되지 않을까? 하는 단순한 생각으로 시작했으나.. 
그렇게 하면 다들 예상하시듯이.. 시간초과가 나옵니다!

 

그래서 두 번째로 생각한 풀이는 이 분 탐 색 입니다.

• min 값은 diff의 최댓값인 100,000부터 시작해 줍니다. (이것보다 큰 값은 있을 수 없으니까요!)
• max 의 시작 값은 diff의 최솟값인 1부터 시작해 줍니다.
• mid = (max+min)/2

이를 이용하여 limit과 계산한 total_time을 비교하며 값을 조정합니다.

• calculateTotalTime(mid) > limit: 숙련도의 값이 더 커져야 하므로 max = mid+1 로 조정합니다. (왼쪽 모든 값을 버림)
• calculateTotalTime(mid) <= limit: 더 작은 숙련도의 값이 존재할 수 있으므로 min = mid-1 로 조정합니다. (오른쪽 모든 값 버림)

int min = 100000; // 문제의 제한 사항 중 diff의 최댓값이 100000 이므로
int max = 1;

while(min>=max) {
	int mid = (min+max)/2;
    int total_time = calculateTotalTime(diffs, times, mid);
    
    if(limit<total_time) {
        max = mid+1;
        mid = (min+max)/2;
    } else {
        min = mid-1;
    }
}

return max;

(2) 코드(Java)

import java.util.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int max = 1;
        int min = 100_000;
        
        while(max<=min) {
            int mid = (max+min)/2;
            long total_time = calculateTotalTime(diffs, times, mid);
            if(total_time > limit) {
                max = mid+1;
            } else {
                min = mid-1;
            }
        }
        
        return max;
    }
    
    static long calculateTotalTime(int[] diffs, int[] times, int level) {
        long total_time = 0;
        int time_prev = 0;
        int time_cur = 0;
        
        for(int i=0; i<diffs.length; i++) {
            time_cur = times[i];
            if(diffs[i]>level) {
                int n = diffs[i]-level;
                total_time += ((long)(n+1)*time_cur + (long)(n*time_prev));
            } else {
                total_time += time_cur;
            }

            time_prev = time_cur;
        }
        return total_time;
    }
    
}