현대 교차로

import sys

lstA, lstB, lstC, lstD = [], [], [], []

cnt = input()
ret = [-1 for i in range(int(cnt))]

tm = 2100000000
for i in range(int(cnt)):
    tmp = input()
    tm = int(tmp.split(' ')[0]) if int(tmp.split(' ')[0]) < tm else tm
    if tmp.split(' ')[1] == 'A':
        lstA.append((int(tmp.split(' ')[0]), i))
    elif tmp.split(' ')[1] == 'B':
        lstB.append((int(tmp.split(' ')[0]), i))
    elif tmp.split(' ')[1] == 'C':
        lstC.append((int(tmp.split(' ')[0]), i))
    elif tmp.split(' ')[1] == 'D':
        lstD.append((int(tmp.split(' ')[0]), i))
    

#0이면 그냥 패스, 1이면 GO, 2이면 교착
while len(lstA) != 0 or len(lstB) != 0 or len(lstC) != 0 or len(lstD) != 0:
    nowA, nowB, nowC, nowD = -1, -1, -1, -1
    if len(lstA) >= 1:
        nowA, aidx = lstA[0]
    if len(lstB) >= 1:
        nowB, bidx= lstB[0]
    if len(lstC) >= 1:
        nowC, cidx = lstC[0]
    if len(lstD) >= 1:
        nowD, didx = lstD[0]
    
    #현재 존재하고, 현 시각 이하로 도착했으며, b가 같이 없는 경우
    if nowA > -1 and nowA <= tm and (nowD == -1 or nowD > tm): 
        ret[aidx] = tm
        lstA.pop(0)
    if nowB > -1 and nowB <= tm and (nowA == -1 or nowA > tm): 
        ret[bidx] = tm
        lstB.pop(0)
    if nowC > -1 and nowC <= tm and (nowB == -1 or nowB > tm): 
        ret[cidx] = tm
        lstC.pop(0)
    if nowD > -1 and nowD <= tm and (nowC == -1 or nowC > tm): 
        ret[didx] = tm
        lstD.pop(0)

    #데드락
    if nowA > -1 and nowA <= tm and nowB > -1 and nowB <= tm and nowC > -1 and nowC <= tm and   nowD > -1 and nowD <= tm:
        break

    tm= tm+1

    #큰 시간차 보정
    if (nowA == -1 or nowA > tm) and (nowB == -1 or nowB > tm) and (nowC == -1 or nowC > tm) and (nowD == -1 or nowD > tm):
        tm = nowA if nowA !=-1 else tm
        tm = nowB if (nowB != -1 and tm > nowB) else tm
        tm = nowC if (nowC != -1 and tm > nowC) else tm
        tm = nowD if (nowD != -1 and tm > nowD) else tm

for i in range(len(ret)):
    print(ret[i])

자꾸 시간초과가 나는 문제가 있었다.

문제조건을 잘 보면, 시간은 10^9까지 존재하지만

자동차 조건은 200000개 뿐이다.

 

도로는 4개이므로, 배열은 80만개를 넘을 수가 없다.

따라서, 공백의 시간이 10^9 - 800000이나 존재한다는 것이므로, 이를 다 찾아보면 시간초과가 뜬다.

 

해결법은, 하나라도 곧 도착할 차가 있는 상황에서, 현재 대기중인 차가 없다면, 바로 가장 빨리 도착할 차가 있는 시간대로 넘어가는 것이다.

큰시간차보정이 그 역할을 수행한다.