Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 | 26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 1차원 DP
- 2차원 dp
- 99클럽
- @BeforeAll
- @BeforeEach
- @Builder
- @Entity
- @GeneratedValue
- @GenericGenerator
- @NoargsConstructor
- @Query
- @Table
- @Transactional
- Actions
- Amazon EFS
- amazon fsx
- Android Studio
- ANSI SQL
- api gateway 설계
- api gateway 필터
- ApplicationEvent
- argocd
- assertThat
- async/await
- AVG
- AWS
- aws autoscaling
- aws eks
- aws iam role
- AWS KMS
Archives
- Today
- Total
기록
[programmers/python] 징검다리 - 이분 탐색으로 바위 사이 최소 거리의 최댓값 찾기 본문
문제 설명
출발지점과 도착지점 사이에 바위들이 놓여 있다. 바위는 특정 위치에 존재하며, 이 중 n개를 제거할 수 있다. 이때 출발, 바위, 도착 사이의 거리 중 최솟값을 최대화하는 것이 목표이다.
예를 들어 다음과 같은 입력이 주어진다:
distance = 25
rocks = [2, 14, 11, 21, 17]
n = 2
- 도착지점까지의 총 거리: 25
- 바위는 위 위치에 존재
- 바위 2개를 제거할 수 있음
우리는 바위 사이의 거리 중 최솟값이 가장 크도록 바위를 제거해야 한다.
핵심 아이디어
이 문제는 다음 질문으로 바꿔 생각할 수 있다:
어떤 최소 거리 x가 주어졌을 때, 그 거리 이상을 유지하기 위해 바위를 몇 개 제거해야 하는가?
이 질문에 답할 수 있으면, 거리 x를 이분 탐색으로 조정하면서조건을 만족하는 가장 큰 x를 찾을 수 있다.
이분 탐색 흐름
- 정답이 될 수 있는 최소 거리의 범위는 1 ~ distance이다.
- 중간값 mid를 기준으로 바위를 제거해가며,
바위 사이 거리가 mid 이상이 되도록 유지해본다. - 제거한 바위 수가 n 이하라면 → 조건 만족 → 거리 늘리기
- 제거 수가 너무 많으면 → 조건 불만족 → 거리 줄이기
구현 코드
def solution(distance, rocks, n):
rocks.sort()
rocks.append(distance)
left, right = 1, distance
answer = 0
while left <= right:
mid = (left + right) // 2
prev = 0
remove = 0
for rock in rocks:
if rock - prev < mid:
remove += 1 # 간격이 부족하면 바위 제거
else:
prev = rock # 바위를 유지한 경우 기준 위치 갱신
if remove > n:
right = mid - 1 # 너무 많이 제거함 → 거리 줄이기
else:
answer = mid # 조건 만족 → 거리 늘릴 수 있는지 확인
left = mid + 1
return answer
예시 흐름
distance = 25
rocks = [2, 14, 11, 21, 17]
n = 2
- 정렬 → [2, 11, 14, 17, 21, 25]
- 예를 들어 mid = 4일 때:
- 거리 4 이상이 되도록 유지하려면 바위 2개만 제거하면 가능
- 조건 만족 → 더 큰 거리로도 가능한지 확인
최종적으로 반환되는 값은 4이며, 이는 바위 사이 거리의 최솟값 중 최대값이다.
'코딩테스트 > python' 카테고리의 다른 글
[programmers/python] 모의고사 - 완전탐색 (0) | 2025.05.21 |
---|---|
[programmers/python] 최소직사각형 - 완전탐색 (0) | 2025.05.21 |
[programmers/python] 입국심사 문제 풀이 - 이분 탐색(Parametric Search) (0) | 2025.05.21 |
프로그래머스_요격 시스템 (0) | 2023.09.10 |
프로그래머스_두 큐 합 같게 만들기 (0) | 2023.06.26 |
Comments