[programmers python] 43236 징검다리

 

programmers.co.kr/learn/courses/30/lessons/43236?language=python3

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

 

 

<problem>

 

 

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

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

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

 

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

 

<constraint>

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

 

---

 

<example>

 

---

 

<solution ①> left, right, mid 변수 활용하여 최솟값 중 최댓값 찾기

 

순서 없이 들어와있는 rocks 값을 우선 정렬 시킨 후 마지막 위치에 distance 값도 추가해줌

 

이분탐색 문제이기 때문에, left, right, mid 변수 활용하여 문제풀이 진행

left = 0, right = distance, mid = (left+right) // 2, min_distance = distance 로 초기화

최소 거리를 min_distance에 저장하고, 바위 삭제 시 del_rock 값 1씩 증가, 현재 위치는 now 변수에 값 저장

 

for문 내에서 현재 위치에서 rock까지의 거리가 mid보다 작다면, 바위 제거

    else: 현재 위치를 rock위치로 이동한 후, min_distance에 거리와 min값 비교하여 저장

for문 완료 시 if del_rock > n: rock 개수 줄이기 위해 right = mid-1

    else: left = mid + 1 answer = min_distance

 

---

 

ⓒ ⓞ ⓓ ⓔ

 

 

---

 

ⓣ ⓔ ⓢ ⓣ

 

---

생각보다 시간이 오래 걸리기도 했고,

코드 자체도 길다는 생각이 들어 줄여보고자 노력

큰 수정은 없음

 

---

 

ⓒ ⓞ ⓓ ⓔ

 

---

 

ⓣ ⓔ ⓢ ⓣ

 

---

 

ⓕ ⓘ ⓝ ⓐ ⓛ    ⓒ ⓞ ⓓ ⓔ