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

문제

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

프로그래머스

 

---

 

문제 개요

각 퍼즐은 난이도와 소요 시간이 주어지며, 퍼즐을 푸는 데 걸리는 시간은 숙련도에 따라 달라진다. 이 문제의 목표는 주어진 제한 시간 내에 모든 퍼즐을 해결하기 위한 최소 숙련도를 찾는 것

 

접근 방법

이진 탐색을 활용하여 숙련도의 최솟값을 찾기 

1. 이진 탐색 초기화: 숙련도의 범위를 1부터 100,000까지 설정
2. 시간 계산 로직 구현: 각 숙련도에 대해 주어진 퍼즐을 해결하는 데 걸리는 총 시간을 계산
3. 시간 초과 체크: 계산된 총 시간이 제한 시간을 초과하는지 확인하고, 이진 탐색 범위를 조정

import java.util.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int first = 1;
        int last = 100_000; 
        int answer = last; 
        
        while (first <= last) {
            int mid = (first + last) / 2;
            long time_total = 0;
            long time_prev = 0; 

            for (int i = 0; i < diffs.length; i++) {
                if (diffs[i] <= mid) {
                    time_total += times[i];
                } else {
                    time_total += (diffs[i] - mid) * (time_prev + times[i]) + times[i]; 
                }
                time_prev = times[i]; 
                if (time_total > limit) {
                    break; 
                }
            }

            if (time_total > limit) {
                first = mid + 1; 
            } else {
                answer = Math.min(answer, mid);
                last = mid - 1;
            }
        }
        
        return answer;
    }
}