프로그래머스 | 퍼즐 게임 챌린지

🔒 문제

프로그래머스 Lv.2 [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지

🔑 해결

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

숙련도의 최소값을 구하여야 하기 때문에, 난이도의 최소값과 최대값 사이에서 결정된다고 가정하고 이진탐색을 수행하였다.
start와 end를 각각 숙련도의 최소값과 최대값으로 부여하고, 중간값의 소요시간을 구하여 소요시간이 제한시간보다 큰 경우 start를 중간값+1로, 소요시간이 제한시간보다 작은 경우 end값을 중간값-1로 변경하였다.

🔓 코드

import java.util.Arrays;
class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;

    int[] levels = diffs.clone();
    Arrays.sort(levels);
    int start = levels[0];
    int end = levels[levels.length-1];

    int mid = start;
    while(start <= end) {
      mid = (start + end) / 2;

      long sum = calculate_time(mid, diffs, times);
      if (sum > limit) {
        start = mid + 1;
      } else {
        answer = mid;
        end = mid - 1;
      }
    }

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

    for (int j = 0; j < times.length; j++) {
      int time_cur = times[j];
      int time_prev = 0;
      if (j > 0) {
        time_prev = times[j-1];
      }

      if (level < diffs[j]) {
        total_time += (time_cur + time_prev) * (diffs[j] - level) + time_cur;
      } else {
        total_time += time_cur;
      }
    }

    return total_time;
  }
}