[Softeer] [인증평가(3차) 기출] 교차로

참고: https://smartshk.tistory.com/51

풀릴 듯 안 풀려서 고민하다가 결국 풀이법을 찾아본 문제. 각 도로를 queue로 구현하면 생각보다 쉽게 풀리는 문제였다.

하나 더 실수했던 점은 중간에 min_time의 초기값을 float인 1e9로 설정했더니 몇 문제에서 오답을 받았다. int로 바꿔주니 해결됐다.

논리 구성

1. 각 도로를 큐로 구현하고, 각 큐에는 차가 들어온 순서 인덱스와 시간을 기록한다. 순서를 기록하는 이유는 출력을 순서 순으로 해야하기 때문이다.

# A를 0으로, D를 3으로 바꿔주는 함수
def get_car_idx(s: str):
    return ord(s) - ord('A')
    
    
queues = [deque([]), deque([]), deque([]), deque([])]
for i in range(N):
    t, w = input().split()
    t = int(t)
    queues[get_car_idx(w)].append((i, t))

2. 초기화
   • 통과가 불가능하면 -1이 나와야하므로 answer를 -1로 이루어진 리스트로 초기화
   • 입력이 0부터 가능하므로 현재 시간 curr_time을 -1로 초기화
   • 교차로를 통과하려는 차량의 존재유무를 담을 is_waiting 리스트를 [0, 0, 0, 0]으로 초기화

answer = [-1] * N
curr_time = -1
is_waiting = [0, 0, 0, 0]

3. 반복문
   • 큐가 하나라도 안 비어있으면 반복
   • 큐의 헤드 원소의 시간이 curr_time보다 작거나 같을 경우 현재 시간보다 일찍 들어와서 기다리고 있는 차량이라는 뜻이므로is_waiting에 해당 큐 표시
   • 기다리고 있는 차량이 4개이면 교착상태라는 뜻이므로 break
   • 기다리고 있는 차량이 0개이면 현재 시간에 들어온 차량이 아직 없다는 뜻이므로 curr_time을 각 큐에 헤드 원소의 시간들 중 가장 작은 시간으로 업데이트 후 continue
   • break나 continue가 진행되지 않았을 경우, 교차로를 통과할 수 있는 차량들은 통과가 된다. 오른쪽 차선에 차가 없을 경우 queue에서 pop해주고 순서 인덱스에 해당하는 answer 리스트의 값을 curr_time으로 업데이트한다.
   • 이후 is_waiting을 다시 [0, 0, 0, 0]으로 초기화하고 curr_time을 1 더해준다.

while queues[0] or queues[1] or queues[2] or queues[3]:
    min_time = int(1e9)
    for i in range(4):
        if queues[i]:
            time = queues[i][0][1]
            min_time = min(min_time, time)
            if time <= curr_time:
                is_waiting[i] = 1
    num_waiting_cars = sum(is_waiting)
    # 교착 상태
    if num_waiting_cars == 4:
        break
    # 새 차가 하나도 없는 상태
    if num_waiting_cars == 0:
        curr_time = min_time
        continue
    for i in range(4):
        if is_waiting[i] and not is_waiting[(i - 1) % 4]:
            idx, _ = queues[i].popleft()
            answer[idx] = curr_time
    for i in range(4):
        is_waiting[i] = 0
    curr_time += 1

4. 마지막에 answer를 출력하면 끝!

print(*answer, sep='\n')

전체 코드

import sys
from collections import deque


def get_car_idx(s: str):
    return ord(s) - ord('A')


def main():
    input = sys.stdin.readline
    N = int(input())
    queues = [deque([]), deque([]), deque([]), deque([])]
    for i in range(N):
        t, w = input().split()
        t = int(t)
        queues[get_car_idx(w)].append((i, t))

    answer = [-1] * N
    curr_time = -1
    is_waiting = [0, 0, 0, 0]
    while queues[0] or queues[1] or queues[2] or queues[3]:
        min_time = int(1e9)
        for i in range(4):
            if queues[i]:
                time = queues[i][0][1]
                min_time = min(min_time, time)
                if time <= curr_time:
                    is_waiting[i] = 1
        num_waiting_cars = sum(is_waiting)
        # 교착 상태
        if num_waiting_cars == 4:
            break
        # 새 차가 하나도 없는 상태
        if num_waiting_cars == 0:
            curr_time = min_time
            continue
        for i in range(4):
            if is_waiting[i] and not is_waiting[(i - 1) % 4]:
                idx, _ = queues[i].popleft()
                answer[idx] = curr_time
        for i in range(4):
            is_waiting[i] = 0
        curr_time += 1
    print(*answer, sep='\n')


if __name__ == '__main__':
    main()