문제
접근
그냥 풀었다가 시간초과가 났다.
1명씩 건너보는 방법으로는 제시간에 풀 수 없다.
특정 x명이 건널 수 있는지 없는지 판단하는 것에 O(n)의 시간이 걸린다.
그럼 x를 조절하면서 건널 수 있는 최대값을 찾는 문제가 되는데,
이는 이분 탐색을 이용하면 건널 수 있는 최대 x를 찾는 시간은 O(logn)의 시간이 필요하다.
최종적으로 O(nlogn)이 걸리므로 가능할 것 같다.
범위는 최소 1명은 건널 수 있으니 1부터 시작하여 최대 가능한 인원은 돌의 크기중 최대값이다.
예를 들어 최대값이 10이고 모든 돌이 10으로 이루어져 있으면, 10명은 무조건 건널 수 있다.
따라서 최대값은 돌의 최대값으로 설정하고 이분탐색을 시작한다.
이 때 최대값이 2인 경우 이분탐색 범위에 들지 않아서 최대값 + 1을 해주었다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def solution(stones, k):
left = 1
right = max(stones) + 1
while left < right - 1:
mid = (left + right) // 2
nowk = 0
flag = True
for stone in stones:
if stone < mid:
nowk+=1
else:
nowk = 0
if nowk == k:
flag = False
break
if flag:
left = mid
else:
right = mid
return left