반응형
250x250
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- 오라클
- 맥북
- Homebrew
- 계정계
- 렌탈스튜디오창업
- 은행IT
- 맥북환경설정
- 맥북셋팅
- union
- 코어뱅킹
- Pass By Value
- 디렉토리계층구조
- oracleapex
- 프로그래머스
- jdk
- fastapi
- SQL
- 인강빨리듣기
- DB
- 채널계
- 컴퓨터공학학사취득
- jdk17
- 모놀리식
- 개인프로필스튜디오창업
- python
- 학점은행제무료강의
- MSA
- it자격증
- 코딩테스트
- 학점은행제
Archives
- Today
- Total
개발머해니
[파이썬] 빠르게 산 오르기 본문
728x90
반응형
실습 설명
신입 사원 장그래는 마부장님을 따라 등산을 가게 되었습니다.
탈수를 방지하기 위해서 1km당 1L의 물을 반드시 마셔야 하는데요. 다행히 등산길 곳곳에는 물통을 채울 수 있는 약수터가 마련되어 있습니다. 다만 매번 줄서 기다려야 한다는 번거로움이 있기 때문에, 시간을 아끼기 위해서는 최대한 적은 약수터를 들르고 싶습니다.
함수 select_stops()는 파라미터로 약수터 위치 리스트 water_stops와 물통 용량 capacity를 받고, 장그래가 들를 약수터 위치 리스트를 리턴합니다. 앞서 설명한 대로 약수터는 최대한 적게 들러야겠죠.
(탈수로 인해서 정상에 도달 하지 못하는 경우는 없다고 가정합니다.)
참고로 모든 위치는 km 단위이고 용량은 L 단위입니다. 그리고 등산하기 전에는 이미 물통이 가득 채워져 있으며, 약수터에 들르면 늘 물통을 가득 채운다고 가정합시다.
예시를 하나 볼게요.
# 약수터 위치: [1km, 4km, 5km, 7km, 11km, 12km, 13km, 16km, 18km, 20km, 22km, 24km, 26km]
# 물통 용량: 4L
select_stops([1, 4, 5, 7, 11, 12, 13, 16, 18, 20, 22, 24, 26], 4)
처음에 4L의 물통이 채워져 있기 때문에, 장그래는 약수터에 들르지 않고 최대 4km 지점까지 올라갈 수 있습니다. 탈수 없이 계속 올라가기 위해서는 1km 지점이나 4km 지점에서 물통을 채워야겠죠?
최대한 적은 약수터를 들르면서 올라가야 하고, 마지막에 산 정상인 26km 지점의 약수터를 들르면 성공적인 등산입니다.
실습 결과
def select_stops(water_stops, capacity):
# 약수터 위치 리스트
stop_list = []
# 마지막 들른 약수터 위치
prev_stop = 0
for i in range(len(water_stops)):
# i 지점까지 갈 수 없으면, i - 1 지점 약수터를 들른다
if water_stops[i] - prev_stop > capacity:
stop_list.append(water_stops[i - 1])
prev_stop = water_stops[i - 1]
# 마지막 약수터는 무조건 간다
stop_list.append(water_stops[-1])
return stop_list
# 테스트 코드
list1 = [1, 4, 5, 7, 11, 12, 13, 16, 18, 20, 22, 24, 26]
print(select_stops(list1, 4))
list2 = [5, 8, 12, 17, 20, 22, 23, 24, 28, 32, 38, 42, 44, 47]
print(select_stops(list2, 6))
[4, 7, 11, 13, 16, 20, 24, 26]
[5, 8, 12, 17, 23, 28, 32, 38, 44, 47]
시간 복잡도
728x90
반응형
'알고리즘' 카테고리의 다른 글
[파이썬] 투자 귀재 규식이 Ⅱ (0) | 2023.09.30 |
---|---|
[파이썬] 중복되는 항목 찾기 Ⅰ (0) | 2023.09.30 |
[파이썬] 거듭 제곱 빠르게 계산하기 (0) | 2023.09.30 |
[파이썬] 투자 귀재 규식이 Ⅰ (0) | 2023.09.30 |
[파이썬] 수강 신청 분석 - 그리디 ★ (0) | 2023.09.30 |