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

https://school.programmers.co.kr/learn/courses/30/lessons/17678

프로그래머스

 

✍️ 문제 요약

다른 크루가 버스 정류장에 도착하는 시간을 알고 있을 때,

게으른 콘이 버스에 탈 수 있으면서 버스 정류장에 가장 늦게 도착하려면 몇 시(HH:MM)에 도착해야 하는지 반환하라.

 

- 버스는 09:00 부터 총 n 회 t 분 간격으로 정류장에 도착하며, 한 버스에는 최대 m 명의 크루가 탈 수 있다.

- 버스에 자리만 있다면, 버스와 동시에 도착한 크루까지 탈 수 있다.

- 콘은 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다.

 

💪 나의 풀이

전체 코드

# n: 셔틀수 (대)
# t: 운행 간격 (분)
# m: 최대 인원 (명)

def hourToMin(str):
    hh, mm = map(int, str.split(':'))
    return hh * 60 + mm

def minToHour(min):
    return '{0:02d}'.format(min//60) + ':' + '{0:02d}'.format(min%60)

def solution(n, t, m, timetable):
    crew_arrival = sorted([hourToMin(x) for x in timetable]) # 크루 도착 시각(분)
    bus_arrival = [540 + i*t for i in range(n)] # 버스 도착 시각(분)
    
    idx = 0 # 이제 버스에 탈 차례인 크루 인덱스 (아직 안 탐)
    cnt = 0 # 각 버스에 탑승한 인원수
    for x in bus_arrival:
        cnt = 0
        while idx < len(crew_arrival) and crew_arrival[idx] <= x and cnt < m: # 크루 탑승 조건
            idx += 1
            cnt += 1
    
    if cnt < m: # 마지막 버스에 자리 남았으면
    	return minToHour(bus_arrival[-1]) # 마지막 버스 도착 시간에 맞춰 도착하면 된다
    else: # 마지막 버스에 자리 안남았으면
        return minToHour(crew_arrival[idx-1]-1) # 마지막으로 탑승한 크루보다 1분 일찍 도착해야 한다

 

세부 설명

편의를 위해 HH:MM의 문자열을 분으로 변경하고, 반대로 분을 HH:MM 형태로 변경하는 hourToMin과 minToHour 함수를 정의한다.

그리고 문제에 나오는 모든 HH:MM 형태의 문자열을 "분"으로 변경해서 생각하자. 

 

문제에서 주어진 timetable을 이용해 크루의 도착 시각을 계산하고 이를 오름차순 정렬한다.

그리고 n과 t를 이용해 버스의 도착 시각을 미리 계산해둔다.

 

이 풀이에서 핵심 로직은, 각 버스를 순회하며 idx와 cnt 변수를 갱신하는 것이라고 생각한다.

- idx: 버스에 탈 차례인 크루 인덱스 (아직은 안 탄 크루)

- cnt: 각 버스에 탑승한 인원 수

idx = 0 # 이제 버스에 탈 차례인 크루 인덱스 (아직 안 탐)
cnt = 0 # 각 버스에 탑승한 인원수
for x in bus_arrival:
    cnt = 0
    while idx < len(crew_arrival) and crew_arrival[idx] <= x and cnt < m: # 크루 탑승 조건
        idx += 1
        cnt += 1

상황적으로 설명하자면, 각 버스가 도착했을 때마다 크루 탑승 조건을 확인하고 크루를 태우는 것이다.

이때 몇 번째 크루까지 탑승했는지, 현재 버스에는 몇 명의 크루가 탑승했는지를 갱신한다.

 

크루 탑승 조건은 위 코드의 while 문에 적힌 순서대로 아래와 같다.

1. 탑승할 크루가 있는지 확인

2. 크루가 버스보다 먼저 도착했는지 (혹은 동시에 도착한 것까지 ok) 확인

3. 버스에 크루가 탑승할 공간이 남아있는지 확인

 

이렇게 버스마다 `idx`와 `cnt`를 갱신하면, for문을 통과했을 때 `idx`와 `cnt`에는 마지막 버스에 대한 정보가 남게 된다.

`idx`는 마지막에 탄 크루의 "다음" 크루 정보로 갱신된다. 즉, 마지막에 탄 크루는 `idx-1` 번째 크루이다.

`cnt`에는 마지막 버스에 몇 명의 크루가 탔는지 정보가 남는다.

 

그럼 이제 머리를 굴려서 콘이 무사히 셔틀을 타고 갈 수 있는 제일 늦은 도착 시간에 대해 고민하면 된다!

결론적으로 (버스를 탈 수 있는 시간 중) 버스 정류장에 제일 "늦게" 도착하려면, "마지막" 버스를 타는 것을 목표로 해야한다.

 

마지막 버스를 타기 위해서는 두 가지 케이스를 고려해야 한다.

1) 마지막 버스에 자리가 남았다면 -> 마지막 버스 도착 시간과 동일하게 도착하는 것이 정류장에 최대한 늦게 도착하는 방법이다.

2) 마지막 버스에 자리가 남아있지 않다면 -> 마지막으로 탑승한 크루보다 1분 먼저 도착해야 마지막 버스를 탈 수 있다.

if cnt < m: # 마지막 버스에 자리 남았으면
    return minToHour(bus_arrival[-1]) # 마지막 버스 도착 시간에 맞춰 도착하면 된다
else: # 마지막 버스에 자리 안남았으면
    return minToHour(crew_arrival[idx-1]-1) # 마지막으로 탑승한 크루보다 1분 일찍 도착해야 한다

 

🤔 다른 사람의 코드를 탐구해보기

전체 코드

# n: 셔틀수 (대)
# t: 운행 간격 (분)
# m: 최대 인원 (명)

def minToHour(min):
    return '{0:02d}'.format(min//60) + ':' + '{0:02d}'.format(min%60)

def solution(n, t, m, timetable):
    answer = ''
    crew_arrival = [int(x[:2])*60 + int(x[3:]) for x in timetable] # 크루 도착 시간(분)
 
    crew_arrival.sort()
 
    last_time = 540 + (n - 1) * t
    if len(crew_arrival) < m: # 크루 수가 버스 정원보다 적다면 충분히 많은 버스가 존재하는 것
        return minToHour(last_time)
        
    for i in range(n):
        # 마지막 버스라면
        if i == n - 1:
            if crew_arrival[0] > last_time: # 탈 순서의 크루가 마지막 버스보다 늦게 도착하니까 어차피 못 탐
                return minToHour(last_time) # 마지막 버스 도착 시간까지 도착하면 된다
            return minToHour(crew_arrival[m-1]-1) # 마지막으로 버스에 탑승하는 크루보다 1분 먼저
        # 마지막 버스가 아니라면
        for j in range(m-1, -1, -1): # j는 m-1부터 0까지
            bus_arrival = 540 + i * t # 버스 도착 시간
            if crew_arrival[j] <= bus_arrival: # 크루가 버스보다 일찍 도착했다면
                del crew_arrival[j] # 리스트에서 크루 제거 (대기 리스트에서 크루 제거)

 

세부 설명

나의 풀이와 다른 부분부터 살펴보자.

 

우선 크루의 수(`len(crew_arrival`)가 버스의 정원(`m`)보다 작은지 확인한다.

만약 작다면 이미 충분히 많은 버스가 존재하는 상황이기 때문에 콘은 마지막 버스 시간(`last_time`)까지만 도착하면 된다.

last_time = 540 + (n - 1) * t # 마지막 버스의 도착 시간
if len(crew_arrival) < m: # 크루 수가 버스 정원보다 적다면 충분히 많은 버스가 존재하는 것
    return minToHour(last_time) # 마지막 버스 시간까지 도착하면 된다

 

그리고 이제 각 버스를 순회하는데, 마지막 버스와 마지막 버스가 아닐 때의 로직이 다르다.

이해를 쉽게 하기 위해 버스의 정원(`m`)이 5라고 가정하자.

 

마지막 버스가 아닐 때

- `crew_arrival` 4번 크루부터 0번 크루까지 역순으로 순회한다.

    - `crew_arrival` 리스트는 이미 오름차순 정렬되어 있는 상태임을 잊지 말자.

- 해당 버스보다 일찍 (혹은 동시에) 도착한 크루만 `crew_arrival` 리스트에서 제거(`del`)한다. (탑승했다는 의미)

for j in range(m-1, -1, -1): # j는 m-1부터 0까지
    bus_arrival = 540 + i * t # 해당 버스 도착 시간
    if crew_arrival[j] <= bus_arrival: # 크루가 버스보다 일찍 도착했다면
        del crew_arrival[j] # 해당 크루 탑승 (대기 리스트에서 크루 제거)

 

마지막 버스일 때

- 이전 버스에 탑승한 크루들은 이미 제거된 상태이기 때문에 `crew_arrival[0]`은 다음 버스에 가장 먼저 탈 크루를 의미한다.

- 이때 `crew_arrival[0]`이 마지막 버스에 탑승할 수 있는지, 없는지에 따라 달라진다.

    - `crew_arrival[0]`가 마지막 버스에 탑승할 수 없다면, 콘은 여유롭게 마지막 버스 시간까지만 도착하면 된다.

    - `crew_arrival[0]`가 마지막 버스에 탑승할 수 있다면, 해당 크루보다 1분 먼저 도착해야 버스에 탑승할 수 있다. (같은 시간에 도착하면 콘의 우선순위가 밀리기 때문)

if crew_arrival[0] > last_time: # 탈 순서의 크루가 마지막 버스보다 늦게 도착하니까 어차피 못 탐
    return minToHour(last_time) # 마지막 버스 도착 시간까지 도착하면 된다
return minToHour(crew_arrival[m-1]-1) # 마지막으로 버스에 탑승하는 크루보다 1분 먼저

 

📚 참고 자료

https://geonlee.tistory.com/39