[HSAT 3회 정기 코딩 인증평가 기출] 교차로

Softeer - [HSAT 3회 정기 코딩 인증평가 기출] 교차로

답

import sys
input = sys.stdin.readline
from collections import deque


t_i = deque();
w_i = deque();
N = int(input())
result = [-1] * N;
for i in range(N):
    t, w = input().split();
    t_i.append(int(t));
    w_i.append(w);

index_A = deque();
index_B = deque();
index_C = deque();
index_D = deque();
index = 0;

for i in w_i:
    if i == 'A':
        index_A.append(index)
        index += 1
    elif i == 'B':
        index_B.append(index)
        index += 1
    elif i == 'C':
        index_C.append(index)
        index += 1
    elif i == 'D':
        index_D.append(index)
        index += 1
    
A, B, C, D = 0, 0, 0, 0; # 각 차선에 있는 차의 수
time = t_i[0]; # 현재 시간
number = 0; # 나간 차의 수
error = 0;

# 맨 처음 같은 시간에 들어온 차들을 전부 waiting_list에 넣고 시작
waiting_list = []

def update():
    global A, B, C, D
    while t_i and t_i[0] == time:
        tmp_1 = t_i.popleft()
        tmp_2 = w_i.popleft()
        waiting_list.append(tmp_2)
        # 차선에 따른 차량 수 증가
        if tmp_2 == 'A':
            A += 1
        elif tmp_2 == 'B':
            B += 1
        elif tmp_2 == 'C':
            C += 1
        elif tmp_2 == 'D':
            D += 1
        # 다음 차량의 도착 시간이 다르면 루프 종료
        if not t_i or tmp_1 != t_i[0]:
            break
                                
update();            


while number != N :
    while A > 0 or B > 0 or C > 0 or D > 0 :
        if A > 0 and B > 0 and C > 0 and D > 0:
            error = 1;
            break;

        elif A > 0 and D == 0:
            if C > 0 and B == 0:
                A -= 1;
                result[index_A.popleft()] = time;
                C -= 1;
                result[index_C.popleft()] = time;
                #print("A, C 통과, time : ", time);
                time = time + 1;
                if t_i and time == t_i[0]:
                    update(); 
                number = number + 2;
                
            else:
                A -= 1;
                result[index_A.popleft()] = time;
                #print("A 통과, time : ", time);
                time = time + 1;
                if t_i and time == t_i[0]:
                    update();   
                number = number + 1;

        elif B > 0 and A == 0:
            if D > 0 and C == 0:
                B -= 1;
                result[index_B.popleft()] = time;
                D -= 1;
                result[index_D.popleft()] = time;
                #print("B, D 통과, time : ", time);
                time = time + 1;
                if t_i and time == t_i[0]:
                    update();   
                number = number + 2;
            else:
                B -= 1;
                result[index_B.popleft()] = time;
                #print("B 통과, time : ", time);
                time = time + 1;   
                if t_i and time == t_i[0]:
                    update();   
                number = number + 1;
                
        elif C > 0 and B == 0:
            if A > 0 and D == 0:
                C -= 1;
                result[index_C.popleft()] = time;
                A -= 1;
                result[index_A.popleft()] = time;
                #print("C, A 통과, time : ", time);
                time = time + 1;
                if t_i and time == t_i[0]:
                    update();   
                number = number + 2;
            
            else:
                C -= 1;
                result[index_C.popleft()] = time;
                #print("C 통과, time : ", time);
                time = time + 1;
                if t_i and time == t_i[0]:
                    update();   
                number = number + 1;
        
        elif D > 0 and C == 0:
            if B > 0 and A == 0:
                D -= 1;
                result[index_D.popleft()] = time;
                B -= 1;
                result[index_B.popleft()] = time;
                #print("D, B 통과, time : ", time);
                time = time + 1;
                if t_i and time == t_i[0]:
                    update();   
                number = number + 2;
            else:
                D -= 1;
                result[index_D.popleft()] = time;
                #print("D 통과, time : ", time);
                time = time + 1;    
                if t_i and time == t_i[0]:
                    update();   
                number = number + 1;
            
            
    
    if error == 1:
        break; 
        
    elif A == 0 and B == 0 and C == 0 and D == 0 and t_i:
        time = t_i[0];
        update();
            
            
for i in result:
    print(i);

풀이

내가 봐도 조금 많이 무식하게 푼 것 같다(부끄렁)
나중에 기회가 된다면 꼭 다시 풀어봐야할 것 같다.

앞으로는 로직을 전부 다 설명하는 것 보단 주요 특징이나 생각하면서 푼 점 위주로 적는게 좋을 것 같아서 이번부터 조금 바꿔보려고 한다.

입력을 받은 다음에 t_i, w_i를 deque 형태로 저장하였는데, 가장 먼저 들어온 차량들을 처리한 다음 지우려고 했다. 처음에는 list 형태로 만들어 pop(0)을 통해 구현했는데, 시간 초과 이슈로 검색을 하다보니 pop(0)은 O(n)이지만, deque의 popleft()는 O(1) 이라고 해서 사용했다.
중간에 index_# 계열 deque()들은 차량이 입력으로 들어온 순서를 저장해둔 다음, 그 순서에 맞춰 출력을 해야하기 때문에 저장하였다. while 문 내에서 필요할 때 마다 index()로 찾으려고 했지만 시간 복잡도를 고려하여 1번만 검색을 하고 이를 deque()에 저장해놨다가 꺼내는 방식으로 복잡도를 줄였다.

마지막으로 while로 반복문을 만들어, 입력받은 수 만큼 차량이 나가야만 반복문이 끝나도록 구현하였고 각 차선(A, B, C, D)에 차량이 있으면 문제 조건에 맞춰 대기했다가 나가는 방식으로 구현했다. 차량이 움직일 수 없는 deadlock 처리 로직과 차량이 들어오는 시간 사이에 텀이 있을 때 처리하는 로직을 추가하여 풀이를 마무리하였다.

---

체점 결과를 보면 조금 많이 틀렸는데, 그 이유로는 **1) 시간 초과** 어쩌면 Python 코딩 테스트의 가장 기본 중 기본인... ``` import sys input = sys.stdin.readline ``` 을 깜빡하고 안 썼다. 쓰기 전에는 평균 시간이 3.09초까지 나왔는데 저 코드 2줄 추가하자마자 0.32초까지 줄었다.. 앞으론 무조건 저 2줄 쓰고 시작해야겠다. 정확하게 말하면 **"반복문으로 여러줄을 입력 받는 문제"** 에서 사용하면 시간이 대폭 줄어드는 것이다.

사용하면서 기억해야 할 점은 sys.stdin.readline()은 한줄 단위로 입력받기 때문에, 개행문자가 같이 입력 받아져 숫자 7을 입력해도 7\n으로 저장되어 type이 str이 된다. map()이나 int()등을 필요에 따라 잘 사용하자.

2) 단순 오답

로직 중 하나를 깜빡했다. 구체적으로 말하면 처음에는

elif A == 0 and B == 0 and C == 0 and D == 0 and t_i:
        time = t_i[0];
        update();

이 코드가 없었는데 때문에 차량이 연속된 시간으로 들어오는 것이 아니라

0 A
100 A

이런 식으로 들어오게 된다면 while문 안에 갇히게 되어 출력이 나오지 않았다. 시간 사이에 공백이 생긴다면, 다음 차량이 들어오는 시간으로 바로 건너뛰도록 코드를 추가하여 해결하였다. 외에는 코드를 수정하는 중간에 복붙을 잘못해서 중간에 update()가 빠진 부분이 있었다... 멘탈 잘 잡고 꼼꼼하게 검사한 다음에 제출하는 습관을 가지면 좋을 것 같다.