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

요구사항

n개 퍼즐의 난이도와 각 퍼즐의 소요 시간이 주어지고 

퍼즐의 난이도보다 숙련도가 낮으면 난이도와 숙련도의 차이 만큼 이전 퍼즐을 다시 풀어야 한다.

주어진 제한 시간 내에 퍼즐을 모두 해결하기 위한 숙련도의 최솟값 구하기

 

 

입력 값

int[] diffs	퍼즐의 난이도 배열
int[] times	퍼즐의 소요 시간 배열
long limit	전체 제한 시간

 

 

풀이

1. 이진탐색을 위해 범위 설정

 

2. 범위 내 중간 값 으로 난이도 가정

 

3. 퍼즐 배열 loop 돌리며 퍼즐 별 푸는 시간 합산

   -> 숙련도보다 퍼즐 난이도가 높은경우

       (이전 퍼즐 소요시간 + 현재 퍼즐 소요시간) * (난이도 - 숙련도) + 현재 퍼즐 소요시간

   -> 숙련도가 퍼즐 난이도보다 높은 경우

 

4. 퍼즐 푸는 시간 합산 값과 전체 제한 시간 비교하여 탐색 범위 재설정

   -> 제한 시간 초과인 경우 범위 시작 지점 조정

   -> 제한 시간 남는 경우 범위 종료 지점 조정

   -> 제한 시간과 퍼즐 푸는 시간이 동일한 경우 현재 임시 난이도가 최소값이므로 return

 

5. 재설정된 범위로 2~4 반복

   -> 범위 시작 지점과 종료 지점이 1이하로 차이나면 종료 지점이 최소값이므로 return

 

 

728x90

Java 코드

import java.util.*;

class Solution {
    public int solution(int[] diffs, int[] times, long limit) {
        int answer = 0;
        
        // 이진탐색용 범위 변수
        int rangeStt = 0;
        int rangeEnd = Arrays.stream(diffs).max().getAsInt();
        
        int tempDiff = 1;
        long totalTime;
        
        while(true){
            // 현재 난이도가 범위 경계인 경우 
            if(rangeEnd - rangeStt <= 1) {
                tempDiff = rangeEnd;
                break;
            }
            
            totalTime = 0;
            
            // 난이도 가정
            tempDiff = rangeStt + ((rangeEnd - rangeStt) / 2);
            
            for(int i = 0; i < diffs.length; i++) {
                if(diffs[i] > tempDiff) // 난이도가 숙련도보다 높은경우
                   totalTime += ((times[i-1] + times[i]) * (diffs[i] - tempDiff)) + times[i];
                else
                    totalTime += times[i];

                // 제한시간 초과 시 break
                if(totalTime > limit) break;
            }

            // 범위 재설정
            if(totalTime > limit)
                rangeStt = tempDiff;
            else if(totalTime < limit)
                rangeEnd = tempDiff;
            else break;
            
        }
        
        answer = tempDiff;

        return answer;
    }
}

 

 

문제 출처

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