🔑 오늘의 학습 키워드 : 이분 탐색
🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/43236
def solution(distance, rocks, n):
left = 0
right = distance
rocks.sort()
rocks.append(distance)
while left <= right:
mid = (left + (right - left) // 2)
prev = 0
removed = 0
for rock in rocks:
if rock - prev < mid :
removed += 1
else :
prev = rock
if removed > n:
break
if removed > n:
right = mid - 1
else :
left = mid + 1
return left-1
🗒️ 공부한 내용 본인의 언어로 정리하기
🤔 문제를 보고 든 생각
distance가 10 ^ 9 인거 보면 일반적으로 풀면 안되고 특별한 생각을 해야겠다는 것을 느낄 수 있다.
이번 문제는 구하라고 하는 것이 두 징검다리의 최소길이의 최대값이다.
그렇다면 이분탐색을 통해 최소 길이에 얼만큼 바위를 뽑는지를 알아보면 된다.
⏰ 예상 시간 복잡도 O(nlogn (정렬)+ log (distance))
2 log 5 * 10 ^ 5 + 9
제한 사항
제한사항
도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
바위는 1개 이상 50,000개 이하가 있습니다.
n 은 1 이상 바위의 개수 이하입니다.
😎 알고리즘 개요
예를 들면 n이 7일때
최소길이 3 -> 5개 뽑음
최소길이 4 -> 5개 뽑음
최소길이 5 -> 6개 뽑음
최소길이 6 -> 7개 뽑음
-> 6 return
이런 식으로 최소길이에 대해 몇개가 뽑히는지를 알아내면서 이분 탐색을 하면 된다.
그러면 1부터 distance까지 거리에서 최소길이(answer)에 n개가 뽑히는 지 알 수 있다.
✅ 오늘의 회고
- 이분 탐색의 경계 조건에 대해 잘 알아야 한다.
- 제한 조건을 파악하여 해당 문제의 알고리즘을 유추할 수 있어야 한다.
#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL
'Coding test' 카테고리의 다른 글
99클럽 코테 스터디 16일차 TIL, 프로그래머스 / N-Queen (0) | 2024.08.06 |
---|---|
99클럽 코테 스터디 15일차 TIL, 프로그래머스 / 소수 찾기 (0) | 2024.08.05 |
99클럽 코테 스터디 13일차 TIL, 프로그래머스 / 입국심사 (0) | 2024.08.03 |
99클럽 코테 스터디 12일차 TIL, 백준 / 1135 / 뉴스 전하기 (0) | 2024.08.02 |
99클럽 코테 스터디 11일차 TIL, 프로그래머스 / 가장 큰 수 (0) | 2024.08.01 |