7/5 Coding Test

✅ 문제 풀이 - Programmers LV4

🎈 징검다리

출발지부터 distance만큼 떨어진 곳에 도착지가 있고 그 사이에 바위들이 존재한다. 바위들의 위치 정보를 담은 배열 rocks가 주어지고 이 바위들 중 n개를 제거해 각 지점 간 거리의 최솟값 중 가장 큰 값을 리턴하는 문제.

• 1 <= distance <= 1e9
• 1 <= n <= 50,000

def solution(distance, rocks, n):
    answer = 0
    rocks.sort()
    rocks.append(distance)
    start, end = 0, distance
    while start <= end:
        mid = (start+end) // 2
        prev = 0
        cnt = 0
        for i in range(len(rocks)):
            curr = rocks[i]
            if curr - prev < mid:
                cnt += 1
            else:
                prev = curr
        if cnt > n:
            end = mid - 1
        else:
            start = mid + 1
            answer = mid
    return answer

< 풀이 과정 >

1. 이진탐색 진행을 위해 주어진 바위 배열을 오름차순 정렬해주고, distance 값을 마지막에 넣어 끝 부분 도착 지점을 지정해준다.
2. 이전 바위 위치 prev, 제거할 바위 수를 cnt로 두고 중간 지점 지정한 이후 for 문으로 바위 위치를 curr로 지정해주어 현재 바위 위치와 이전 바위 위치 간 거리 차이를 구한다.
3. 거리 차이가 mid 보다 작다면 이전 바위를 제거 처리 해준다.
4. 제거할 바위 수가 n보다 크면 끝 지점에서 -1 처리, 아닌 경우 시작 위치 + 1 처리하여 중간 지점을 결과로 리턴해준다.

오랜만에 코테를 진행해서 그런지 1시간 좀 넘게 오래 걸린 문제.
노트에 손으로 직접 써가면서 이진 탐색 구현을 진행했다.
바위 제거 시점, 바위 위치 변경 시점이 핵심이었던 문제.