[Javascript] 프로그래머스 - 퍼즐 게임 챌린지

🧾 목차

1. 문제 설명

2. 문제 풀이

3. 정답 코드

4. 총평

---

1. 문제 설명

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

 

퍼즐 해결 시 소요 시간 계산 방법

예제 조건

- 퍼즐 난이도 : 1,5,3

- 퍼즐당 기본 시간 : 2,4,7

- 나의 레벨 : 1

 

계산 과정

1. 첫 번째 퍼즐 (난이도 1, 시간 2)

- 내 레벨(1)과 같으므로, 소요 시간 = 2

 

2. 두 번째 퍼즐 (난이도 5, 시간 4)

- 난이도 (5) > 내 레벨(1)이므로 추가 시간 발생

 

- 추가 시간 공식

  👉 (이전 퍼즐 소요 시간 + 현재 퍼즐 소요 시간 ) x (퍼즐 난이도 - 내 레벨) + 현재 퍼즐 소요 시간

 

- 적용

  (2 + 4) x (5 - 1) + 4 = 6 x 4 + 4 = 24 + 4 = 28

- 총 소요 시간 = 28

 

3. 세 번 째 퍼즐 (난이도 3, 시간 7)

- 계산해보시오

 

주의 할점

- 퍼즐 난이도가 내 레벨보다 크면 추가 시간이 필요함

- 공식을 올바르게 적용하여 누적시간 계산해야 함

---

2. 문제 풀이

제한사항을 보다시피 굉장히 큰 수이므로, 이분탐색으로 접근한다.

 

⭐ 시간 복잡도

1) 완전탐색

만약 이분탐색을 사용하지 않고 모든 반복을 수행한다면?

레벨 :  1 <= diffs[i] <= 100,000
퍼즐의 길이 : 1 <= diffs.length <= 300,000

👉 레벨 x 퍼즐의 길이 = 3 x 10^10 (시간초과!!)

 

2) 이분탐색

그렇다며 이분탐색으로 최소 레벨을 찾는 시간복잡도는? 

이분탐색을 적용한 레벨 찾기 : log(n) = log(10^5) ≃ 20
퍼즐의 길이 : 위와 동일

👉 레벨 x 퍼즐의 길이 = 6 x 10^6 (만족)

 

코드 풀이

1) 초기화

이분탐색으로 나의 레벨을 찾기 위해 [left, right]를 [최소 레벨, 최대 레벨] 로 세팅한다.

 

2) 이분 탐색

단계 1. 중간 값 찾기

단계 2. 소요 시간을 계산

단계 3. 범위를 조정

 

if elapsed == limit 👉 mid를 즉시 리턴해도됨!

---

3. 정답 코드

MAX_MY_LEVEL = 100000;

function solution(diffs, times, limit) {
    var [left, right] = [1, 100000]; // 최소 레벨, 최대 레벨
    
    while (left <= right) {
        var level = Math.floor((left + right) / 2); // 중간 값 계산
        
        // 소요시간을 계산
        var elapsed = 0;
        for (let i = 0; i < diffs.length; i++) {
            if (diffs[i] > level) {
                elapsed += ((times[i] + times[i-1]) * (diffs[i] - level)) + times[i];
            } else {
                elapsed += times[i];
            }
        }
        
      
        // 범위를 조정
        if (elapsed > limit) { // 소요시간이 더 많을 경우
            left = level + 1;
        } else { 
            right = level -1;
        }
    }
    
    return left;
}

 

---

4. 총평

이 문제는 직접 해결하지 못했다.

그 이유는 문제 파악을 제대로 하지 않아 소요 시간을 계산하는 로직을 틀렸기 때문이다.

이처럼, PCCP 문제는 특히 문제가 길고, 예제가 복잡하다는 것을 알 수 있었다.

문제 파악이 잘 되지 않을 때, 풀이보다는 예제를 통해 이해를 충분히 하고 넘어가야한다는 것을 다시 한번 느꼈다..내 시간.....