해당 글은 프로그래머스 문제 풀이를 기반으로 작성했습니다.
문제 - https://programmers.co.kr/learn/courses/30/lessons/43236
징검다리
문제 설명
출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.
예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.
제거한 바위의 위치 | 각 바위 사이의 거리 | 거리의 최솟값 |
[21, 17] | [2, 9, 3, 11] | 2 |
[2, 21] | [11, 3, 3, 8] | 3 |
[2, 11] | [14, 3, 4, 4] | 3 |
[11, 21] | [2, 12, 3, 8] | 2 |
[2, 14] | [11, 6, 4, 4] | 4 |
위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.
출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
- 바위는 1개 이상 50,000개 이하가 있습니다.
- n 은 1 이상 바위의 개수 이하입니다.
입출력 예
distance | rocks | n | return |
25 | [2, 14, 11, 21, 17] | 2 | 4 |
시행착오
해당 문제를 먼저 이분탐색을 생각하지 않고 코딩을 해봤습니다. 하지만 이분탐색과 같은 검색 알고리즘 문제에서는 "효율성" 테스트가 중요합니다. 효율성을 고려해야하는 코드인가를 알기 위해선 제한사항을 파악하면 됩니다. 주어진 문제의 제한사항을 보면 distance와 rocks는 1~1,000,000,000(10억)이하, 그리고 1~50,000이하의 개수를 가집니다.
즉, distance와 rocks를 for문과 같은 loop문의 range로 설정이 되면 큰 숫자일 때 효율성이 좋지 않으면 runtime이 너무 오래 걸리는 문제가 발생합니다. 비효율적인 코드가 되는거죠! 제가 처음에 그냥 막 짠 코드도 for문의 iteration쪽을 보면 rocks의 조합을 구하고, filtered_rocks의 조합을 구하게 짜뒀는데 rock가 5만개가 될 수 있는 점(시간복잡도가 O(n^2))을 생각하면 .. 실행시간을 보더라도 매우 비효율적인 코드라는 점을 알 수 있습니다. 최대한 적은 회수로 rock간의 최소 거리를 찾는 것이 중요하다는 것을 알 수 있습니다.
실패코드
from itertools import combinations
import numpy as np
def solution(distance, rocks, n):
'''
distance(int): 출발지점에서 도착지점까지의 거리
rocks(list): 바위들이 있는 위치
n(int): 제거할 바위의 수
'''
answer = 0
sorted_rocks = list(sorted(rocks))
between_dist_min = []
for i, j in combinations(rocks, 2):
filtered_rocks = sorted_rocks[:]
filtered_rocks.remove(i)
filtered_rocks.remove(j)
between_dist = []
for idx, num in enumerate(filtered_rocks):
# print(i, j)
if idx == 0:
between_dist.append(num)
else:
between_dist.append(num-filtered_rocks[idx-1])
if idx == len(filtered_rocks)-1:
between_dist.append(distance-num)
# print(between_dist)
between_dist_min.append(min(between_dist))
answer = max(between_dist_min)
return answer
실행시간
정확성 | 테스트 |
테스트 1 〉 | 실패 (111.29ms, 27.8MB) |
테스트 2 〉 | 실패 (103.16ms, 27.8MB) |
테스트 3 〉 | 실패 (133.98ms, 28MB) |
테스트 4 〉 | 실패 (시간 초과) |
테스트 5 〉 | 실패 (시간 초과) |
테스트 6 〉 | 실패 (시간 초과) |
테스트 7 〉 | 실패 (시간 초과) |
테스트 8 〉 | 실패 (시간 초과) |
테스트 9 〉 | 통과 (0.02ms, 27.8MB) |
성공코드
참고 코드: https://cocook.tistory.com/84
# 참고 코드: https://cocook.tistory.com/84
def solution(distance, rocks, n):
start = 1
end = distance
# 이분탐색을 하기 위한 정렬
rocks.sort()
while start < end:
# 13,
mid = (start+end)//2
# print("mid 업데이트: ", mid)
cnt = 0
pre_rock = 0
for rock in rocks:
# 간격이 mid보다 작으면 제거
if rock-pre_rock < mid:
cnt += 1
# print("간격: ", rock-pre_rock, "개수: ", cnt)
# 간격이 mid보다 같거나 크면 기준 위치 업데이트
else:
pre_rock = rock
# 제거 개수가 주어진 제거 개수보다 크면 왼쪽으로 간 후 break
if cnt > n:
end = mid
# print("end 업데이트: ", end, "start: ", start)
break
# 제거할 바위가 남아있는 경우, 오른쪽으로
else:
start = mid+1
# print("start 업데이트: ", start, "end: ", end)
return start-1
출력예시와 코드 설명
문제에서는 주어진 바위들의 위치에서 n개의 바위를 제거했을 때의 최소 간격들 중 최대값을 구하는 것입니다. 다시 말하면, 주어진 바위 위치들에서 최소 간격을 가지는 바위 n개를 제거해내면 됩니다. <=> n+1번째로 작은 바위 사이의 간격을 구하면 됩니다.
이를 이분탐색으로 풀 때, 이분탐색의 target이 되는 값은 바위 사이의 간격입니다. 이분탐색의 전제는 sorting된 리스트입니다. 따라서 rocks라는 바위 간격이 저장된 리스트를 정렬해준 후, 시작합니다. 바위사이의 간격은 바위끼리 겹쳐지는 경우가 없으므로 0이 아니라, start값이 1로 시작됩니다. 그리고 가장 큰 바위의 간격은 가장 끝에 있는 바위의 위치이므로 end값은 distance로 초기화됩니다. 따라서, 시작하는 mid값은 (1+distance)//2가 되므로 예시 값에서 (1+25)//2 = 13이 됩니다.
mid값을 start와 distance로 계산해서 초기화한 후, rocks의 값들과 비교합니다. for문 내의 코드는 mid값보다 기준 바위와 현재 살펴보는 바위의 간격이 작으면 제거 대상이 되는 것으로 카운트하는 것입니다. 그리고, mid값보다 같거나 크면 현재 살펴보는 바위를 기준 바위로 업데이트해줍니다. cnt 개수가 n보다 커지고, 기준되는 바위가 업데이트된 후가 우리가 찾는 n+1번째로 작은 바위 사이의 간격입니다.
참고로, 보통의 타겟값을 찾는 이분탐색의 문제같은 경우 if 조건문에 cnt가 들어가는 것이 아니라, if 찾고자 하는 값 == mid 되는 케이스에 대해 찾습니다.
# example
distance = 25
rocks = [2, 14, 11, 21, 17]
n = 2
solution(distance, rocks, n)
# output
mid 업데이트: 13
간격: 2 개수: 1
간격: 11 개수: 2
기준 바위 업데이트: 14
간격: 3 개수: 3
end 업데이트: 13 start: 1
mid 업데이트: 7
간격: 2 개수: 1
기준 바위 업데이트: 11
간격: 3 개수: 2
간격: 6 개수: 3
end 업데이트: 7 start: 1
mid 업데이트: 4
간격: 2 개수: 1
기준 바위 업데이트: 11
간격: 3 개수: 2
기준 바위 업데이트: 17
기준 바위 업데이트: 21
start 업데이트: 5 end: 7
mid 업데이트: 6
간격: 2 개수: 1
기준 바위 업데이트: 11
간격: 3 개수: 2
기준 바위 업데이트: 17
간격: 4 개수: 3
end 업데이트: 6 start: 5
mid 업데이트: 5
간격: 2 개수: 1
기준 바위 업데이트: 11
간격: 3 개수: 2
기준 바위 업데이트: 17
간격: 4 개수: 3
end 업데이트: 5 start: 5
4