문제 링크
https://programmers.co.kr/learn/courses/30/lessons/17678
코딩테스트 연습 - [1차] 셔틀버스
10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00"
programmers.co.kr
풀이 - 다른 블로그 참고
1. 시간 계산을 쉽게 하기 위해 'HH:MM' 형식의 시간을 모두 분으로 crew_list 변환해서 저장
예 ) 09 : 00 는 9 * 60 + 0
2. 먼저 온 크루가 앞에 오도록 crew_list 정렬
3. 9:00부터 t분 간격으로 n번 도착하는 버스 도착 시간 bus_list에 저장
4. 버스가 도착할 때마다 버스에 타는 크루 수 저장
5. 버스에 자리가 남는 경우 콘은 마지막 버스 도착 시간에 오면 됨
or 버스에 자리가 없을 경우 콘은 맨 마지막에 버스에 탄 크루보다 1분 먼저 도착하면 됨
def solution(n, t, m, timetable):
answer = 0
# 크루 도착 시간 저장
crew_list = []
# 버스 도착 시간 저장
bus_list = []
# 크루 도착 시간 분으로 바꿔서 저장
for i in timetable:
h_time, m_time = map(int,i.split(":"))
crew_list.append(h_time*60 + m_time)
# 먼저 도착한 크루 순으로 정렬
crew_list.sort()
# 첫 버스 도착 시간 9 : 00
tmp = 9 * 60
bus_list.append(tmp)
# 버스 도착 시간 저장
for _ in range(n-1):
tmp += t
bus_list.append(tmp)
# 탑승할 크루 인덱스
i = 0
# 버스 도착 시간마다
for bus_time in bus_list:
# 해당 버스 도착 시 탑승한 크루 수
cnt = 0
# 탑승한 크루 수보다 탑승할 수 있는 수가 많을 때
# 탑승할 크루가 있을 때
# 탑승할 크루의 도착 시간이 버스 도착시간과 같거나 빠를 때
while cnt < m and i < len(crew_list) and crew_list[i] <= bus_time :
i += 1
cnt += 1
# 버스에 탑승할 자리가 남아있으면, 버스 도착한 시간에 도착하면 됨
if cnt < m :
answer = bus_time
# 버스에 탑승할 자리가 없으면, 마지막으로 탑승한 크루의 도착시간보다 1분 일찍
else :
answer = crew_list[i-1] - 1
return str(answer//60).zfill(2) + ":" + str(answer%60).zfill(2)
+ 2022.04.25 다시 풀이
- heapq 사용해서 풀이
import heapq
# 시간 분으로 바꾸기
def time_to_min(s):
s = s.split(':')
hour = int(s[0]) * 60
minute = int(s[1])
return hour + minute
# 분을 출력 형식에 맞는 시간으로 바꾸기
def min_to_time(t):
hour = str(t // 60)
minute = str(t % 60)
return hour.zfill(2) + ":" + minute.zfill(2)
def solution(n, t, m, timetable):
answer = 0
arrive = []
# 도착하는 시간 기준으로 최소 힙 구현
for i in timetable:
heapq.heappush(arrive, time_to_min(i))
# 버스 시작 시간
start = time_to_min('09:00')
for _ in range(n) :
# 셔틀에 타는 승객 수
cnt = 0
# 마지막 탑승한 승객의 도착 시간
last_t = 0
while arrive :
# 셔틀보다 늦게 도착하면 중단
if arrive[0] > start :
break
# 셔틀이 꽉 찼으면 중단
if cnt == m :
break
# 승객 태우기
last_t = heapq.heappop(arrive)
cnt += 1
# 셔틀에 아직 탈 수 있으면
if cnt < m :
# 셔틀 도착시간
answer = start
# 셔틀이 꽉 찼으면
else :
# 마지막으로 탑승한 승객보다 1분 빨리 와야 탈 수 있음
answer = last_t - 1
# 다음 셔틀 시간 갱신
start += t
return min_to_time(answer)
n = 10
t = 60
m = 45
table = ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"]
print(solution(n,t,m,table))
'개발 > algorithm' 카테고리의 다른 글
[프로그래머스][level3] 광고 삽입 -python (0) | 2022.01.22 |
---|---|
[프로그래머스][level3] 표 편집 -python (0) | 2022.01.22 |
[백준 1463번] 1로 만들기 -python (0) | 2022.01.20 |
[프로그래머스][level3] 거스름돈 -python (0) | 2022.01.18 |
[프로그래머스][level3] 야근 지수 -python (0) | 2022.01.18 |