99클럽 코테 스터디
오늘의 문제도 굉장히 어려웠다. 발표시간 전에 풀 수 있을까 하는 확신이 없어서 발표 신청도 못했다. 결국 발표시간 전에 풀긴 했지만, 다른 분이 먼저 풀고 발표하셨다.
그래서 오늘도 챌린저 문제만 TIL로 작성했다.
챌린저 문제 징검다리 : https://school.programmers.co.kr/learn/courses/30/lessons/43236
출처 : 프로그래머스
챌린저 문제 : 징검다리
풀이 접근
answer를 이분탐색으로 구하는 게 중요하다.
이걸 생각하지 못해서 굉장히 오래 걸렸다.
나는 answer를 구하는 것 말고도 특정 거리 이상을 이동한 바위를 찾는 데도 이분탐색을 썼다. 다 풀고 나서 생각해 보았는데, 이 부분은 오히려 시간복잡도상 손해 같다. 그냥 앞에서부터 탐색하면 O(r)인데, 밟을 바위가 아주 많을 경우에는 이분탐색으로 모두 찾으면 O(nlogr)이 되는데 이게 rlogr에 근접하기 때문이다. (r은 바위 수, n은 남길 바위 수이다. 문제에서 주어진 n은 바로 쓰기 불편해서 바꾸었다)
이 부분이 아쉬워서, 바위 탐색은 그냥 앞에서부터 탐색하는 걸로 바꿔서도 풀어 보았다. (코드2)
그리고 이분탐색의 디테일이 틀려서, 11~19번 테스트케이스가 자꾸 틀리는 일이 있었다. 이 부분도 고치느라 조금 시간이 걸렸다.
코드1(Python3, 통과, 최대 1526.47ms, 12.3MB)
r은 바위의 수이다. 그리고, 문제의 조건상, 시작점과 끝점도 rocks에 포함시키는 게 편하다. 그래서 끝점은 바위에 그냥 대놓고 append해서 포함시키고, 시작점(0)은 인덱스 -1에 넣었다. (시작점은 rocks의 개수를 셀 때 포함 안 시켰다. 이 쪽이 ddn 구하기 편하기 때문)
다 풀고 생각해보니 그냥 둘 다 append한 다음에 sort해도 별 문제는 없을 것 같다.
binary_search 함수는, left번째 바위에서 오른쪽으로 dist 거리 이상 떨어져 있는 가장 가까운 바위의 번호를 return하는 함수이다.
d_left와 d_right는, 각각 이론상 가능한 answer의 최소값과 최대값으로 시작한다. 그리고 이 둘을 가지고 이분탐색을 하여, answer가 되는 조건을 만족하는 거리의 최댓값을 찾는다.
if r + i <= n + p or distance - rocks[p] < d_mid * (n - i): 부분은, 남은 바위들로 d_mid만큼씩 이동할 수 있는 최소 조건이 만족하지 않는 경우로, 더 탐색하지 않고 가지치기하여 d_mid는 answer가 될 수 없음을 결정짓는 부분이다.
def solution(distance, rocks, n):
rocks.sort()
rocks.append(distance)
r = len(rocks)
n = r - n
if n == 1:
return distance
rocks.append(0)
ddn = distance // n # distance divided by n
def binary_search(left, dist): # left : 위치, dist : 거리, 위치는 실제 위치가 아닌 rocks의 index
right = r - 1
goal = rocks[left] + dist
while left < right:
mid = (left + right) // 2
if rocks[mid] < goal:
if left == mid:
return right
left = mid
else:
right = mid
return left
d_left = 0
d_right = ddn
while d_left < d_right:
d_mid = (d_left + d_right + 1) // 2
p = -1
d_mid_possible = True
for i in range(n):
if r + i <= n + p or distance - rocks[p] < d_mid * (n - i):
d_mid_possible = False
break
p = binary_search(p, d_mid)
if d_mid_possible:
d_left = d_mid
else:
if d_right == d_mid:
break
d_right = d_mid
return d_left코드2(Python3, 통과, 최대 234.48ms, 12.3MB)
binary_search 함수를 그냥 앞에서부터 순회하는 search 함수로 바꿨다. 결과가 이 쪽이 훨씬 좋다.
상술한 if r + i <= n + p or distance - rocks[p] < d_mid * (n - i): 조건에서 가지치기를 먼저 하므로, search 함수 자체에는 불가능한 경우를 고려한 예외처리를 하지 않았다.
def solution(distance, rocks, n):
rocks.sort()
rocks.append(distance)
r = len(rocks)
n = r - n
if n == 1:
return distance
rocks.append(0)
ddn = distance // n # distance divided by n
def search(posi, dist): # posi : 위치, dist : 거리, 위치는 실제 위치가 아닌 rocks의 index
goal = rocks[posi] + dist
while True:
posi += 1
if rocks[posi] >= goal:
return posi
d_left = 0
d_right = ddn
while d_left < d_right:
d_mid = (d_left + d_right + 1) // 2
p = -1
d_mid_possible = True
for i in range(n):
if r + i <= n + p or distance - rocks[p] < d_mid * (n - i):
d_mid_possible = False
break
p = search(p, d_mid)
if d_mid_possible:
d_left = d_mid
else:
if d_right == d_mid:
break
d_right = d_mid
return d_left