[이분탐색] 징검다리

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

문제설명

출발지점부터 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 이상 바위의 개수 이하입니다.

1차 코드

# 거리의 최소값은 시작지점으로 부터 첫 바위까지 거리인 min(rocks) 이지만 효율을 위해 0
# _high = distance 
# rock이 50000개 이하니까 sort해도 괜찮나,,?

def solution(distance, rocks, n):
    rocks.sort(key = lambda x:x)
    low = 0
    high = distance # 모든 바위가 없는 경우
    ans = []
    num = len(rocks) + 2 - n # 놓인 바위 개수 + 출발, 끝지점바위 - 제거할 바위 개수
    # mid값이 최소값 중 가장 큰 값이 될 것이라 가정
    # 탐색에서 제외할 것은 mid보다 작은 돌들.. 작은 돌들의 개수가 num을 넘겼다면 mid 조정
    
    # 바위사이 거리
    ans.append(rocks[0]) #시작돌까지 거리
    for i in range(len(rocks)):
        try:
            ans.append(rocks[i+1]-rocks[i])
        except:
            pass
    ans.append(distance-rocks[-1]) #끝부터 마지막돌사이 거리
    
    #최소값 출력하기 
    while len(ans) >= num:
        mid = (low+high)//2 
        for dis in ans:
            if dis < mid:
                ans.pop(0)
                high = mid + 1
            else:
                low = mid - 1 
    return max(ans)

처참하게 실패한 테스트 케이스들 .. 다시 보면 틀릴 수 밖에 없는 알고리즘이다.

1차 코드의 문제점 고치기

그리고, 바위를 넣어둔 상태에서 반복문을 돌렸는데 거기서 ans.pop(0)을 써서 바위를 진짜 뺐다. 바위를 집어 넣고 뺀 다음의 거리 계산을 한 다음 돌아가게 만들었는데, pop연산 대신 다른 방법이 필요할 것 같다.

위 사진은print(a, dis, low, mid, high)로 출력한 사진이다.
1차 코드를 실행해보면 위 예시처럼 무한 루프에 빠지게 되는데 이걸 탈출할 조건을 찾아내줘야 한다. 패턴 상으로 보면 low - high = 2로 루프를 돌고 있으니, low와 mid와 high 값 변경 때 오류가 있는 것 같다.

그리고, 앞에선 pop연산으로 케이스에 따라 바위 거리 배열의 값을 진짜 pop했는데, 배열 전체를 도는 pop(0)연산 대신 빼내는 바위 수를 저장할 변수 r과 빼낸 바위사이거리 dis 변수를 이용해 팝을 대신해 바위빼내기를 구현해보자.

2차 코드

# 거리의 최소값 = min(items) 이지만 효율을 위해 0
# _high = distance
# rock이 50000개 이하니까 sort해도 괜찮나,,?

def solution(distance, rocks, n):
    rocks.sort(key = lambda x:x)
    low = 0
    high = distance # 모든 바위가 없는 경우
    ans = []
    
    # mid값이 최소값 중 가장 큰 값이 될 것이라 가정
    # 탐색에서 제외할 것은 mid보다 작은 돌들.. 작은 돌들의 개수가 num을 넘겼다면 mid 조정
    
    # 바위사이 거리
    ans.append(rocks[0])
    for i in range(len(rocks)):
        try:
            ans.append(rocks[i+1]-rocks[i])
        except:
            pass
    ans.append(distance-rocks[-1]) 
    
    #최소값 출력하기 
    while high - low > 1:
        mid = (low+high)//2 
        dis = 0 # 바위 제거 후 거리 계산값
        r = 0 # 뺀 바위 수
        for a in ans:
            dis += a # 바위 뺌
            if dis < mid: 
                r += 1	# 탐색 제외할 바위 개수 증가
            else:
            	# dis > mid : 최소값중 큰 값 나타남
                dis = 0 # 바위 중간값 초기화
        if r > n: # 바위 뺀 다음 뺀 개수가 n을 넘는다면
            high = mid # 많이 빼지 않는 선에서 최대값을 구할거임
            # 탐색범위를 낮추고 재탐색
        else:
        # r<n :
            low = mid # 더 많이 빼도 최대값을 구해낼 수 있다. 탐색범위 올림
    return low

        

TIL

• 이 문제는, 매개변수로 주어진 배열을 가공하는 단계가 필요했다. 가공하기 위한 최적의 방법을 생각해내고, 거기에 low와 high를 조정하는 조건과 바위 개수를 조정하는 설정을 찾아낸 과정을 잘 기억해두자

1. distance의 범위가 개 크게 나타남 고로 이분탐색
2. 조정될 놈은 변동값이다. 주어진 입출력 예에서 변동하는 값은 배열인 제거할 바위와 최소값이 있는데, 이전값과 비교하며 조정가능한 거리의 최솟값을 mid값으로 둬보겠음
3. 탐색 범위는 출발지점(0)~도착지점(distance)까지이다

• ans배열을 돌면서 바위를 뺀다.
• mid 값보다 빼면서 더한 바위사이 총 거리값인 dis가 작으면 돌을 더 빼내고, 크면 그 거리를 초기화한다.
• 초기화하면 그 다음 스텝에서 분기점이 발생한다
  1. r > n : 돌을 너무 많이 뺐다. 최대값이 되기 까지 지정한 돌 보다 더 많이 뺐어야 하므로 상한선을 낮춘다
  2. r < n : 돌이 적게 빠졌다. 조금만 빼도 mid값이 넘어가므로 mid는 최대값이 아니다. 하한선을 mid로 끌어올린다.

참고 문제집