29 공유기 설치
- 1회: 오답 - 문제에 대한 감도 못 잡음, 문제를 이해하고 나니 떡볶이 떡 문제랑 비슷하단 걸 알았다
모범답안: github.com/ndb796/python-for-coding-test/blob/master/15/3.py
해설
- 집의 좌표와 공유기의 갯수(C)를 입력 받기
- 집의 좌표를 정렬하기
- 집끼리의 최대 거리를 구하기 위한 이진탐색 수행
- 맨 처음에 mid는 중간점: (첫번째 집 좌표 + 마지막 집 좌표) // 2
- 항상 첫번째 집부터 공유기를 설치한다고 할 때, 공유기 사이의 간격이 mid를 만족하는 집의 갯수를 찾는다. (마지막 집까지 찾기)
- 설치한 공유기의 갯수가 C보다 크거나 같으면,
- answer = mid로 저장
- mid 값을 늘이고: start 포인트의 지점을 뒤로 이동. start = mid + 1
- 설치한 공유기의 갯수가 C보다 작으면,
- mid 값을 줄이고: end 포인트의 지점을 앞으로 이동. end = mid - 1
- 이진탐색을 완료하면 answer 반환
n = 5
c = 3
array = [1, 2, 4, 8, 9]
start = 1
end = array[-1] - array[0]
answer = -1
while start <= end:
mid = (start + end) // 2
value = array[0]
count = 1
for i in range(1, n):
if array[i] >= value + mid:
count += 1
value = array[i]
if count >= c:
answer = mid
start = mid + 1
else:
end = mid - 1
return answer
'CS기초 > 코딩테스트' 카테고리의 다른 글
LeetCode 20 (Easy) Valid Parentheses (0) | 2021.03.23 |
---|---|
LeetCode 232 (Easy) Implement Queue using Stacks (0) | 2021.03.23 |
LeetCode 35 (Easy) Search Insert Position (0) | 2021.03.11 |
LeetCode 349 (Easy) Intersection of Two Arrays (0) | 2021.03.11 |
LeetCode 278 (Easy) First Bad Version (0) | 2021.03.11 |