[PS] 프로그래머스 [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 java 풀이 (14번에서 틀린 이유)

 

https://school.programmers.co.kr/learn/courses/30/lessons/340212?language=java

프로그래머스

초기 문제 접근

1. level 값을 때려 맞춰야할 것 같으니 이분 탐색을 떠올렸다.
2. 문제 시나리오 대로, diff <= level이면 timeCur만 더한다.
3. diff가 더 높으면 i가 0 일 경우 total += (long) (diff - level) * timeCur + timeCur;
   i가 0보다 클 경우 total += (long) (diff - level) * (times[i - 1] + timeCur) + timeCur;   
4. 총 퍼즐 풀이 시간이 limit보다 작게 걸렷다면 end = mid - 1, answer값 갱신해주고 다시 loop
   더 오래 걸렸다면 start = mid + 1

14번에서 틀림

start를 0부터 시작해서 그렇다. diffs 값의 범위가 1부터 시작하기 때문에, 숙련도가 0이 되는 경우가 생기면 답이 0이 되어버린다.

예를 들어, start = 0, end = 10 이면 end -> 5 -> 2 -> 1 이렇게 될 수도 있다.

이 경우 반례는 이렇다.

int[] diffs = {1};
int[] times = {10};
long limit = 20;

start = 0, end = 1이면 level = 0이고 diffs가 1이므로

total = (1 - 0) * 10 + 10 = 20 인데 결국 limit와 같아지므로 answer = level.

결과적으로 정답이 answer = 0이 되어버린다.

코드

import java.util.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        int start = 1;
        int end = 100000;
        
        while (start <= end) {
            int level = (start + end) / 2;
            long total = 0;
            
            // check
            for (int i = 0; i < diffs.length; i++) {
                int diff = diffs[i];
                int timeCur = times[i];
                
                if (diff <= level) {
                    total += timeCur;
                } else {
                    if (i == 0) {
                        total += (long) (diff - level) * timeCur + timeCur;
                    } else {
                        total += (long) (diff - level) * (times[i - 1] + timeCur) + timeCur;   
                    }
                }
            }
            
            if (total <= limit) {
                answer = (int) level;
                end = level - 1;
            } else {
                start = level + 1;
            }
        }
        
        return answer;
    }
}