징검다리 건너기
https://school.programmers.co.kr/learn/courses/30/lessons/64062
문제 설명
징검다리를 통해 건너편으로 건너려고 합니다.
규칙
1. 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.
2. 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.
3. 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.
4. 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.
디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.
풀이 설명
특정 값을 찾는 문제로 이분 탐색을 통해 해결가능하다.
특정 숫자보다 작은 수가 연속되는 k개를 찾는 것
- 이분 탐색을 통해 mid 값을 설정
- mid 보다 작은 값들의 수를 저장
- 만약 작은 값의 수가 k보다 크면 mid는 answer의 후보 중 하나
- 이분 탐색 반복
def solution(stones, k):
answer = 0
length = len(stones)
s = sorted(set(stones))
left, right = s[0], s[-1]
while left <= right:
# 1, mid 값은 이미 건넌 인원 수를 의미
mid = (left+right) // 2
m = 0 # 최댓값
l, cnt = [], 0
# 2
for i in stones:
if i <= mid:
cnt += 1
else:
l.append(cnt)
cnt = 0
else :
l.append(cnt)
m = max(l)
# 이 경우 mid가 3, cnt가 6이 나와 answer = 3
# left = 1, right = 2로 이분탐색 시작
# 바로 answer을 반환하지 않는 이유
# 만약 정답이 3인데 처음 mid 값이 6이다고하면
# right 값을 줄여나가면서 cnt>=k인 가장 작은 mid 값을 찾는게 목적이다.
if m < k:
left = mid + 1
else:
answer = mid
right = mid - 1
return answer오답 노트
처음 접근은 단순하게 반복문으로 stones를 -1하고 0의 수가 연속해서 k개 이상이면 answer을 return하게 코드를 작성했고 당연히 시간초과가 뜸
