문제 설명 및 제한사항
아이디어 및 해결 방법
코드
def is_promising(distance, rocks, th, maxskips):
rocks = [0] + rocks + [distance]
nskips, i, j = 0, 0, 1
# rocks[j] == distance이면 j를 스킵할 수 없음에 주의합니다.
while j < len(rocks):
# rocks[i] ~ rocks[j] 사이의 간격이 th 이상이 되도록
# skip해서 j를 옮깁니다.
while j < len(rocks) and rocks[j] - rocks[i] < th:
j += 1
nskips += 1
if nskips > maxskips:
return False
i, j = j, j+1
return True
def solution(distance, rocks, n):
# 돌 사이 간격의 최솟값을 mid로 설정하고, mid가 간격 중 최솟값이
# 되도록 돌을 배치할 수 있는지 판단해서 mid를 조정하는 이분탐색 문제입니다.
rocks.sort()
l, r = 0, distance
mid = (l + r) // 2
# 돌 사이에 mid보다 작은 간격이 없도록 할 때,
# 최소의 skip 횟수가 n보다 커져 버리면 mid를 줄여야 하고
# n보다 크거나 같으면 mid를 키워도 됩니다.
while l < r:
mid = (l + r) // 2
if is_promising(distance, rocks, mid, n):
answer = mid
l, r = mid+1, r
else:
l, r = l, mid
return answer
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges