[프로그래머스 / 이분탐색/ Python] 징검다리

문제 설명

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.
예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

 

위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

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

 

제한사항

• 도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
• 바위는 1개 이상 50,000개 이하가 있습니다.
• n 은 1 이상 바위의 개수 이하입니다.

문제에 나온 예와 같습니다.

 

 

---

풀이 코드

def solution(distance, rocks, n): rocks.sort() answer = 0 start = 0 end = distance while start <= end: mid = ( start + end ) // 2 count = 0 pre = 0 for rock in rocks: if rock - pre < mid: count += 1 else: pre = rock if count > n: break if count <= n: start = mid + 1 answer = mid else: end = mid - 1 return answer

---

풀이 과정

이 문제 또한 알고리즘 챕터 별로 풀지 않았으면 시간 내에 절때로 풀지 못했을 문제였다. 문제 해답은 입국심사와 비슷한 풀이다.

def solution(distance, rocks, n): rocks.sort() answer = 0 start = 0 end = distance while start <= end: mid = ( start + end ) // 2 count = 0 pre = 0

1. 정렬되어있지 않은 rocks list를 정렬해준다.

2. 시작점은 0 가장 끝에있는 돌은 distance로 지정해준다.

3. 이진탐색을 하기 위해 while문을 작성한다. 이때 while의 조건은 시작점이 끝점보다 작거나 같을 때 while문 안에 있는 내용들을 수행하도록 한다.

4. 이진탐색을 수행하기 위해 시작점과 끝 점의 거리를 2로 나눈 값을 mid로 설정하고(최솟값 중 최댓값을 찾는거라 mid를 기준으로 탐색한다), 이후에 필요한 변수 count와 pre변수는 loop를 돌때마다 초기화 해준다.

 for rock in rocks: if rock - pre < mid: count += 1 else: pre = rock if count > n: break

5. rocks에 있는 값들을 하나씩 꺼내며 이전값과의 차이가 mid보다 작으면 count를 증가시킨다. count는 제거하는 돌 개수이다. 만약 mid보다 값이 크면 돌을 제거할 필요 없이 pre값을 현재의 rock값으로 바꾼다.

ex)
rocks = [1,2,6,10] 이렇게 있고 mid = 3 일 경우
첫번째 for 루프에선 rock(1) - pre = 1 이기 때문에 count += 1을 한다. (1을 제거)
두번째 for 루프에선 rock(2) - pre = 2 이기 때문에 2또한 제거하여 count += 1을 하게 된다.
세번째 for 루프에선 rock(6) - pre = 6 이기 때문에 mid보다 값이 커 이때는 6을 제거하지 않고 pre 값을 6으로 바꾼다.
네번째 for 루프에선 rock(10) - pre(6) = 4 가 된다. 이때도 mid값 보다 커서 10을 제거하지 않고 pre를 10으로 바꾼다.


6. 만약 count가 n보다 크면 더 이상 for 문을 돌릴 필요가 없으므로 loop를 빠져나간다.

 if count <= n: start = mid + 1 answer = mid else: end = mid - 1 return answer

count가 n보다 작거나 같은 것은 상관없다. 왜냐하면 최소 중 최댓값을 구하는 문제이기 때문이다.

코드를 보면 직관적으로 답을 선택하는 범위가 큰 것에서 작은 것으로 점차 줄어드는 것을 알 수 있다.


7. count가 n보다 작다는 것은 다음을 의미한다.
① 돌들의 차이가 mid 값 보다 작은 것들의 개수는 이미 충족되었다. (제거하지 않은 돌들 중 아무거나 제거해도 mid값보단 크거나 같다)
② answer의 값은 mid보다 크거나 같을 것이다.

해서 answer에 mid의 값을 미리 저장해 둔다.

극단적인 예를 들자면
만약 n =2 일 때 mid가 7일때는 count가 1이었는데, mid가 8일 때 count = 3이 된다면 답은 answer = 7이 된다. 왜냐하면 제거한 개수(1)을 제외하고 그 중 어떤 값을 제거해도 남은 돌들의 차이는 7보다는 크거나 같은 값이 되기 때문이다.



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

코딩테스트 연습 - 징검다리