[PCCP 기출 2번] 퍼즐 게임 챌린지

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

프로그래머스

 

 

문제 난이도

 - Lev2

 

문제 유형

- 이진 탐색(binary Search)

- 구현

 

문제 분석

• 퍼즐의 난이도와 소요시간이 주어진다.
• 만약 나의 숙련도보다 퍼즐의 난이도가 같거나 낮다면, 퍼즐의 소요 시간만큼 퍼즐을 푸는데 소요된다.
• 만약 나의 숙련도보다 퍼즐의 난이도가 높다면
• 틀린 횟수 = 나의 숙련도- 퍼즐의 난이도
  • 전체 소요 시간 =  + 틀린 횟수 * (현재 퍼즐을 푸는데 걸린 시간 + 이전 퍼즐의 문제 풀이 시간) +  현재 퍼즐을 푸는데 걸린 시간
• 만약, 제한 시간(limit) 내의 해당 퍼즐을 풀지 못할 경우, 숙련도를 낮춰서 내가 풀 수 있는 숙련도의 최솟값을 구해야 한다.

해당 문제를 처음 접근했을 때, 지문만 읽고, 이전 퍼즐의 문제 풀이 시간이 1번 퍼즐문제부터 현재 이전까지의 문제 풀이 시간을 모두 더한 것이 이전 퍼즐의 문제 풀이 시간인 줄 알았다가, 예시를 보고 그냥 현재 바로 이전의 문제 풀이 시간만 더한다는 것을 알았다.

 

또한, binarySearch를 할 때, mid 값을 설정해주는 곳에서 무한루프가 돌아서 다시 차근차근 계산하면서 level-1을 할지를 고민하였다.

 

전체 코드

다음은 전체 코드이다.

import java.util.*;
import java.io.*;

/**
* 퍼즐 : 난이도, 소요시간
* 나의 레벨: level
* 퍼즐의 난이도: diff, 퍼즐의 소요 시간: time_cur, 이전 퍼즐의 소요 시간: time_prev
* 
* if(diff <= level) solved (time_cur);
* else solved in (diff - level) * time_cur + time_prev -> 이전 문제를 다시 풀고 와야함;
* time_prev = time_cur * 이전 문제의 개수
* 
* 퍼즐의 난이도: diffs, 소요시간:times, 제한시간: limit
* 제한시간내의 퍼즐을 모두 해결하는데 필요한 최소 숙련도
* bianrySearch
*/

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        int N = diffs.length;
        
        int minLevel = 100_001;
        int maxLevel = 0;
        
        for(int i = 0; i < N; i++) {
            if(diffs[i] > maxLevel) maxLevel = diffs[i];   
            if(minLevel > diffs[i]) minLevel = diffs[i];
        }
        
        int result = maxLevel;
        while(minLevel < maxLevel) {

            int level = (minLevel + maxLevel) >> 1;
            long time = 0;
            int time_prev = 0;
            for(int i = 0; i < N; i++) {
                
                if(level >= diffs[i]) {
                    time += times[i];
                } else {
                    int cnt = diffs[i] - level;
                    
                    // 문제 해결
                    if(i != 0) time += ((times[i] + times[i-1]) * cnt + times[i]);
                    else time += times[i] * (cnt+1);
                }
            }
            
            if(time <= limit) {
                if(result > level) {
                    result = level;
                }
                maxLevel = level;
            } else {
                minLevel = level + 1;
            }
        }
        
        return result;
    }
}