[프로그래머스] 퍼즐 게임 챌린지 (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을 설정하고 중간 값으로 시간 안에 풀리는지 확인하도록 구현하자.

 

 

코드

	def solution(diffs, times, limit):
	max_level = max(diffs) #최대 diff 구해두기
	l = 1
	r = max_level
	answer = max_level #정답이 max_diff인 경우를 대비해서 answer에 넣어두기
	while l < r:
	level = int((l + r) /2)
	time = times[0]
	for i in range(1, len(diffs)):
	k = 0
	if level < diffs[i]:
	k = diffs[i] - level
	time += (times[i] + times[i -1]) * k + times[i]
	if time <= limit:
	r = level
	answer = level
	#구간이 좁아질때마다 항상 문제를 시간안에 풀 수 있는 r을 정답으로 설정
	else:
	l = level +1
	#현재 level은 정답이 아니므로 범위 자체에서 제외
	return answer

view raw pccp2puzzle.py hosted with ❤ by GitHub