[백준 24511번] 문제풀이

# 오답 이유 : 시간초과

import sys
input = sys.stdin.readline
# 배열의 갯수
n = int(input())

# 배열의 형식 (stack, queue)
dataA = list(map(int, input().split()))

# 배열에 들어갈 숫자
dataB = list(map(int, input().split()))

# 수열의 갯수
m = int(input())

# 수열
c = list(map(int,input().split()))

#결과값 저장
result = []

# 수열의 갯수만큼 반복문 시작
for i in range(m):
    # 배열의 갯수만큼 2중 반복문 시작
    for j in range(n):

        # 쓸대없는 리스트 삭제
        # listTest = []
        # listTest.append(dataB[j])
        # listTest.append(c[i])

        # 만약 수열의 형식이 큐라면
        if dataA[j] == 0:
            # c[i] 값과 dataB 값을 바꿔줌
            dataB_1 = c[i]
            c[i] = dataB[j]
            dataB[j] = dataB_1

        # 배열의 구조가 스택일 시 그냥 스킵해도 됨
        # else:
        #     c[i] = dataB[-1]
        # dataB[j] = c[i]

    # 최종적으로 바뀐 c[i]값을 result에 append
    result.append(c[i])
    
#출력
print(*result)

위와 같은 코드로 구현을 성공하고 제출하니 시간초과가 떴다.

당연히 맞을 줄 알았는데 2중 포문에 if문까지 써서 시간복잡도가 엄청나게 올라간것 같다.

 

그래서 아래와 같이 코드를 수정하고 제출하니 정답이 나왔다.

# 이 문제의 특이점은 deque라는 기능과 파이썬의 for else문을 사용한다는 거다.
import sys

# 원하는 방향에서의 append와 pop이 가능한 deque라는 기능을 선언해준다.
from collections import deque

# 시간복잡도 개선을 위한 명령어
input = sys.stdin.readline

# 문제를 푸는데 필요한 값을 모두 입력받는다.
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
m = int(input())
c = list(map(int, input().split()))

# 문제의 deque 기능의 선언
# deque 는 stack과 queue의 모든 특성을 가지고 있는 자료형의 구조이다.
queStack = deque()

# 자료구조의 양만큼 반복문을 시작한다.
for i in range(n):
    # 만약 a[i] 값이 queue일경우
    # stack은 입력과 출력이 일어나도 변수의 변경이 없으므로 생략해준다.
    if a[i] == 0:
        # deque에 b[i] 값을 차례대로 append 해준다.
        queStack.append(b[i])
# 반복문이 종료 된 후 바로 실행되는 else 명령어.
else:
    # 만약 b 리스트 내부가 모두 스택이여서 len(b)의 값이 0일경우
    if len(b) == 0:
        # 그냥 c에 입력된 수열을 다시 출력해준다.
        # stack 자료형에 들어간 수는 어차피 pop을 해도 다를게 없기때문
        print(*c)
        # 코드 즉시 종료
        sys.exit()

# 이제 입력한 수열의 값을 queStack에 넣어 pop해준다.
for i in range(m):
    # queStack 내부 가장 왼쪽에 수열의 값을 넣어준다.
    queStack.appendleft(c[i])
    # queStack 마지막 자료를 pop 해주고 출력.
    print(queStack.pop(), end=" ")