문제
https://school.programmers.co.kr/learn/courses/30/lessons/64062
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
주요 아이디어
최대 몇 명까지 징검다리를 건널 수 있는지 return해야 하는 이분탐색 문제이다.
- "최대로 건널 수 있는 명 수"를 이분탐색 타깃으로 둔다
- 건널 수 있는지, 없는지를 판별
- 건널 수 있으면 인원을 증가
- 건널 수 없으면 인원을 감소
코드 구현 (Python 3)
더보기
def can_check(bridge, people, k):
# 0 이하 구간이 연속되는 최대 횟수
cnt = 0
for stone in bridge:
# 뛰어 넘을 수 없는 칸 : 남은 칸수 - 사람 수 음수면 못뛰어넘는 칸 +1
if stone < people:
cnt += 1
if cnt >= k:
return False
else:
cnt = 0
return True
def solution(stones, k):
start, end = 0, max(stones)
max_people = 0
while start <= end:
mid = (start + end) // 2
# print('## people : ', mid)
# 건널 수 있다는 뜻
if can_check(stones.copy(), mid, k):
max_people = max(max_people, mid) # 최대값 갱신
start = mid + 1
# 건널 수 없으면
else:
end = mid - 1
return max_people
제출 결과
'알고리즘 > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 폰켓몬 (0) | 2024.05.21 |
---|---|
[프로그래머스] 행렬의 곱셈 (0) | 2024.05.21 |
[프로그래머스] 문자열 다루기 기본 (0) | 2024.05.21 |
[프로그래머스] 가장 먼 노드 (0) | 2024.05.21 |
[프로그래머스] 단어 변환 (0) | 2024.04.11 |