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

문제

 

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

프로그래머스

 

 

풀이

 

난이도: Lv.2

 

 

일단 정답은 문제들 중 최대 diff(난이도) 만큼의 level(숙련도)의 이하일 것이다.

level 최대 diff보다 높아도 이미 모든 문제를 한 번의 시도로 풀 수 있기 때문에 의미가 없다.

 

따라서 1 ~ max_diff 사이에 정답이 있다.

가장 간단히는 max_diff부터 순서대로 숙련도를 1씩 줄이면서 시간 안에 문제를 풀어보는 브루트 포스 방법을 생각할 수 있다.

하지만 diff는 최대 100,000이고 퍼즐이 최대 300,000 개이므로,

최악의 경우 대략 30,000,000,000 (300억)번의 연산이 발생하므로 시간 초과가 발생한다.

(Python보다 빠른 C++이라도 10억번 이상의 연산은 시간 초과 발생.)

 

 

 

이처럼 시간 복잡도가 극단적인 경우 다른 방법을 생각해야 한다.

특정 구간(여기서는 1~ max_diff)에서 정답을 맞추는 경우는 업다운 게임처럼 가운데 숫자를 확인해서 구간을 반씩 좁혀나가는 이진 탐색이 효과적이다.

이진 탐색은 O(nlogn)의 시간복잡도 이므로 충분히 시간안에 해결가능하다.

 

 

왼쪽 끝인 l와 오른 쪽 끝인 r을 설정하고 중간 값으로 시간 안에 풀리는지 확인하도록 구현하자.

 

 

코드