[Python] 프로그래머스 Lv4_징검다리

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

프로그래머스

 

• 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있음
• 그리고 그사이에는 바위들이 놓여있음
• 바위 중 몇 개를 제거하려고 함

 

• 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면
• 출발지점, 도착지점, 바위 간의 거리가 아래와 같음
• 이때, 거리의 최솟값 중 가장 큰 값은 4

 

 

• 출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return

 

제한사항

• 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하
• 바위는 1개 이상 50,000개 이하
• n 은 1 이상 바위의 개수 이하

 

"""
입출력 예시)

distance = 25, rocks = [2, 14, 11, 21, 17], n = 2 -> 4
"""

 

 

## 의사 코드 ##

# 탐색 범위가 100만 이상 -> 이분탐색 

# 이분탐색 전제 조건: 정렬
# rocks.sort() 

# left = 0
# right = distance

# 현재 거리 => 각 바위 사이의 거리의 최솟값 중 가장 큰 값
# mid = (left + right) // 2

# 현재 제거한 바위의 수 
# delete = 0

# 이전 바위의 위치
# prev_rock = 0 

# 바위 사이의 거리를 구했을 때 mid 보다 작으면 제거, 크면 그대로 두기
# for rock in rocks:
#     dist = rock - prev_rock
#     if dist < mid: delete += 1
#     else: prev_rock = rock 

# <현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 많으면 탐색 범위를 작은 쪽으로 줄이기

# <현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 같거나 작으면 탐색 범위를 큰 쪽으로 줄이기

 

 

 

통과한 코드

 

def solution(distance, rocks, n):
    answer = 0
    # 바위의 위치 오름차순 정렬 
    rocks.sort()
    left, right = 0, distance 

    while left <= right:
        # 현재 거리 => 각 바위 사이의 거리의 최솟값 중 가장 큰 값
        mid = (left + right) // 2
        # 현재 제거한 바위의 수 
        delete = 0
        # 이전 바위의 위치 (시작: 시작지점인 0)
        prev_rock = 0 

        for rock in rocks:
            # 현재 바위와 이전 바위 사이의 거리 
            dist = rock - prev_rock
            # 바위 사이의 거리가 mid보다 작으면 바위 제거
            if dist < mid:
                delete += 1
            # 바위 사이의 거리가 mid보다 같거나 크면 이전 바위의 위치를 현재 바위 위치로 변경 
            else:
                prev_rock = rock 
            # <현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 많으면 break  
            if delete > n:
                break 
        
        # <현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 많으면 탐색 범위를 작은 쪽으로 줄이기
        if delete > n:
            right = mid - 1
        # <현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 같거나 작으면 탐색 범위를 큰 쪽으로 줄이기
        else:
            answer = mid
            left = mid + 1

    return answer

 

 

 

• 과정 확인

distance = 25
rocks = [2, 14, 11, 21, 17]
n = 2

"""
left: 0, right: 25
현재 거리(mid): 12 

현재 바위의 위치: 2, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 2 

현재 바위의 위치: 11, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 11 

현재 바위의 위치: 14, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 14 

현재 바위의 위치: 17, 이전 바위의 위치: 14
현재 바위와 이전 바위 사이의 거리(dist): 3 

현재 제거한 바위의 수(delete): 3 

<현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 많은 경우
갱신된 right: (mid - 1) = 11
------------------------------
left: 0, right: 11
현재 거리(mid): 5 

현재 바위의 위치: 2, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 2 

현재 바위의 위치: 11, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 11 

현재 바위의 위치: 14, 이전 바위의 위치: 11
현재 바위와 이전 바위 사이의 거리(dist): 3 

현재 바위의 위치: 17, 이전 바위의 위치: 11
현재 바위와 이전 바위 사이의 거리(dist): 6 

현재 바위의 위치: 21, 이전 바위의 위치: 17
현재 바위와 이전 바위 사이의 거리(dist): 4 

현재 제거한 바위의 수(delete): 3 

<현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 많은 경우
갱신된 right: (mid - 1) = 4
------------------------------
left: 0, right: 4
현재 거리(mid): 2 

현재 바위의 위치: 2, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 2 

현재 바위의 위치: 11, 이전 바위의 위치: 2
현재 바위와 이전 바위 사이의 거리(dist): 9 

현재 바위의 위치: 14, 이전 바위의 위치: 11
현재 바위와 이전 바위 사이의 거리(dist): 3 

현재 바위의 위치: 17, 이전 바위의 위치: 14
현재 바위와 이전 바위 사이의 거리(dist): 3 

현재 바위의 위치: 21, 이전 바위의 위치: 17
현재 바위와 이전 바위 사이의 거리(dist): 4 

현재 제거한 바위의 수(delete): 0 

<현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 같거나 작은 경우
갱신된 left: (mid + 1) = 3
------------------------------
left: 3, right: 4
현재 거리(mid): 3 

현재 바위의 위치: 2, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 2 

현재 바위의 위치: 11, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 11 

현재 바위의 위치: 14, 이전 바위의 위치: 11
현재 바위와 이전 바위 사이의 거리(dist): 3 

현재 바위의 위치: 17, 이전 바위의 위치: 14
현재 바위와 이전 바위 사이의 거리(dist): 3 

현재 바위의 위치: 21, 이전 바위의 위치: 17
현재 바위와 이전 바위 사이의 거리(dist): 4 

현재 제거한 바위의 수(delete): 1 

<현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 같거나 작은 경우
갱신된 left: (mid + 1) = 4
------------------------------
left: 4, right: 4
현재 거리(mid): 4 

현재 바위의 위치: 2, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 2 

현재 바위의 위치: 11, 이전 바위의 위치: 0
현재 바위와 이전 바위 사이의 거리(dist): 11 

현재 바위의 위치: 14, 이전 바위의 위치: 11
현재 바위와 이전 바위 사이의 거리(dist): 3 

현재 바위의 위치: 17, 이전 바위의 위치: 11
현재 바위와 이전 바위 사이의 거리(dist): 6 

현재 바위의 위치: 21, 이전 바위의 위치: 17
현재 바위와 이전 바위 사이의 거리(dist): 4 

현재 제거한 바위의 수(delete): 2 

<현재 제거한 바위의 수(delete)>가 [제거할 바위의 수(n)]보다 같거나 작은 경우
갱신된 left: (mid + 1) = 5
------------------------------

4
"""

 

 

 

 

 

참고)

 

https://cocook.tistory.com/84

[프로그래머스] 징검다리 파이썬

 

 

https://velog.io/@jqdjhy/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC-%ED%8C%8C%EC%9D%B4%EC%8D%AC