본문 바로가기

개발/algorithm

[프로그래머스][level3] [1차] 셔틀버스 -python

문제 링크

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))