[Python] 프로그래머스. 2019 카카오 겨울 인턴 recruit - 징검다리 건너기 (Level 3)

https://programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스

19년 12월 처음 접했을 때는 시간이 없어서 못 풀었고, 이번에 풀었을 때 효율성 13번에서 시간초과가 난 문제.

 

공식 풀이는 이분탐색.

나는 이 문제를 '전체 list 중 k개를 window로 돌면서, 해당 window의 최댓값이 가장 작은 것'을 반환하는 문제라고 봤다.

 

window로 돌 때, 해당 window 모든 값이 0이면 더 이상 강을 건널 수 없다.

모든 값이 0이 되려면, window의 가장 큰 값도 0이 되어야 하기 때문.

 

비슷한 알고리즘으로 푸신 듯한 다른 분의 C++코드.

[알고리즘] 카카오 개발자 겨울 인턴십 코딩 테스트 풀이

 

동일한 로직의 코드로 풀었을 때 실제 시험에서는 통과했고, 공개한 연습문제 테스트에서는 시간초과가 났다고 하는 걸 보니

13번 테스트 케이스의 기준이 올라갔나 보다.

 

	from collections import deque
	def solution(stones, k):
	window = deque(stones[:k])
	loc_max = max(window)
	global_min = loc_max
	for i in range(k, len(stones)):
	leftpop = window.popleft()
	rightappend = window.append(stones[i])
	if leftpop == loc_max:
	loc_max = max(window)
	global_min = min(global_min, loc_max)
	return global_min

view raw [프로그래머스] 징검다리 건너기.py hosted with ❤ by GitHub

 

이분탐색으로 푼 코드

 

	def solution(stones, k):
	_min, _max = 0, max(stones)
	answer = 0
	while _min <= _max:
	mid = (_min + _max) // 2
	arr = []
	zero_in_row = 0
	max_zeros = zero_in_row
	for i in range(len(stones)):
	if stones[i] >= mid:
	arr.append(stones[i])
	elif stones[i] < mid:
	arr.append(0)
	if arr[i] == 0:
	zero_in_row += 1
	elif arr[i] != 0:
	max_zeros = max(max_zeros, zero_in_row)
	zero_in_row = 0
	max_zeros = max(max_zeros, zero_in_row)
	if max_zeros >= k:
	_max = mid - 1
	else:
	answer = mid
	_min = mid + 1
	return answer

view raw [프로그래머스] 징검다리 건너기_이분탐색.py hosted with ❤ by GitHub