[Softeer 인증평가 3차] 교차로(파이썬)

https://softeer.ai/practice/info.do?idx=1&eid=803&sw_prbl_sbms_sn=169039 

Softeer

문제접근

 

for문을 돌려서 시간대로 차를 집어넣는다면

100% 시간초과가 뜰 문제.

시간 최대값이 10^9이므로

일일이 직접 시간을 전부 돌릴 수는 없다.

그래서 queue를 4개 선언한 다음

각 위치에 차량을 진입시킨다.

 

자세한 풀이

 

1. deque각각에 차량 번호+진입시간을 apppend

deque 4개로 이뤄진 배열을 선언한 후

ord를 활용해서 deque에 하나씩 넣어줍니다.

 

2. 각 배열의 deque가 모두 빌 때까지 반복해줍니다.

현재차량 배열을 두고

맨 앞의 차량의 차량시간을 봅니다.

(이 문제는 친절하게 오름차순으로 변수를 줬는데

만약 이런 설명이 없으면 따로 sort시켜줘야할듯)

현재시간보다 진입시간이 작으면 진입시켜줍니다.

 

3. 만약 모든 차가 진입해있다면 

아무 차도 갈 수 없기 때문에 반복을 중단합니다.

만약에 어떤 차도 진입되어있지 않다면

현재시간을 현재 맨 앞 차의 최소시간으로 바꿔주고 continue

 

4. 차가 하나라도 있다면 차를 진입시켜줍니다.

이 때, 이전 번호차가 없어야합니다.

A는 D

B는 A

C는 B

D는 A

A,C가 동시에 있으면 서로 나갈 수 있지만

A,D가 동시에 있다면 서로 가로막혀서 못나갑니다.

저는 A까지는 염두하지 않아서 이 점 때문에 해멨습니다.

 

코드

import sys
from collections import deque

N = int(input())

answer = []
car = [deque() for _ in range(4)]

# 큐에 각 위치에 들어갈 자동차 저장

for num in range(N):
    t, w = input().split()

    go = ord(w) - ord('A')
    car[go].append((int(t), num))

answer = [-1] * N
nowTime = 0
# 자동차를 모두 진입할 때까지 큐를 돌림
while car[0] or car[1] or car[2] or car[3]:

    minT = int(1e9)
    nowCar = [0] * 4

    for d in range(4):
        if car[d]:
            cTime, cNum = car[d][0]
            minT = min(minT, cTime)
            # 현재시간보다 작거나 같다면 진입시킨다
            if cTime <= nowTime:
                nowCar[d] += 1

    nowBusy = sum(nowCar)
    # 차 4개가 한번에 다 들어가있다면 아무것도 못들어가기 때문에 que를 끝낸다
    if nowBusy == 4:
        break
    # 차가 아무것도 없다면 시간을 up하고 다음 큐로
    elif nowBusy == 0:
        nowTime = minT
        continue

    # 지금 들어가있는 차 차례대로 뽑기
    for d in range(4):
        # 차가 진입할 조건:차가 있고 이전 칸에 차가 없어야함.
        # A번 진입이라면 D에 차가 없어야 가능함(이거 생각못할 수 있음. 주의)
        if nowCar[d] and nowCar[(d - 1) % 4] == 0:
            _, carNum = car[d].popleft()
            answer[carNum] = nowTime

    nowTime += 1

for i in range(N):
    print(answer[i])