[Python] 프로그래머스. 징검다리 (Level 4)

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

코딩테스트 연습 - 징검다리 | 프로그래머스

이분탐색 문제.

distance 제한사항이 1,000,000,000인 것에서 이분탐색 느낌이 강하게 오긴 했지만,

이분탐색에서 기준으로 삼을 값이 뭔지 도저히 감이 안 와서 다른 블로그 해설을 참고해야만 했다.

 

이분탐색의 기준은 '돌과 돌 사이의 거리' 였고, 이분탐색을 진행하는 방법은

1. '돌과 돌 사이의 거리가 이분탐색 기준값보다 작을 경우 뒤쪽 돌을 삭제한다'

2. 삭제한 돌의 개수가 기준 n보다 클 경우 돌과 돌 사이의 거리를 줄이고, n보다 작거나 같을 경우 거리를 늘리는 식으로 이분탐색을 진행한다.

 

'무엇을 이분탐색 값으로 설정할 것인지', '이분탐색의 left, right값을 변화시킬 기준은 무엇인지' 익숙해지는 게 왜 이리 어려운지 모르겠다.

 

 

	import math
	def solution(distance, rocks, n):
	rocks.sort()
	rocks.append(distance)
	left, right = 0, distance
	# 바위 사이의 최소거리보다 거리가 작을 경우 돌 삭제.
	# 거리가 클 경우, 이 값들 중 최솟값을 구해둔다.
	answer = 0
	while left <= right:
	# 이전 돌
	prev = 0
	# 돌 거리 최솟값.
	mins = math.inf
	# 제거한 돌 개수
	removed_rocks = 0
	# 바위 사이의 최소거리
	mid = (left + right) // 2
	# 각 돌을 돌면서 제거할 돌을 찾는다.
	for i in range(len(rocks)):
	if rocks[i] - prev < mid:
	removed_rocks += 1
	else:
	mins = min(mins, rocks[i] - prev)
	prev = rocks[i]
	# 제거한 돌 개수가 기준보다 많다 = 바위 제거를 줄여야 한다.
	# 바위 사이 최소거리의 기준을 낮춰야 한다
	if removed_rocks > n:
	right = mid - 1
	# 제거한 돌 개수가 기준보다 적다 = 더 많은 바위 제거가 필요
	# = 바위 사이 최소거리 기준을 높여야 한다
	else:
	answer = mins
	left = mid + 1
	return answer

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