백준) queuestack

문제) queuestack

 

해당 문제는 문제를 이해하기 까지 조금 시간이 오래 걸린 문제였다. 한글로 이루어진 문제인데 왜 해독이 어려운지...

어찌 되었든 해당 문제는 문제의 설명에 나와 있는 데로 큐 또는 스택을 pop을 하여 마지막에 pop 이된 변수를 따로 저장하여 따로 저장된 변수들을 한줄로 출력해야 하는 문제였다

 

그리고 주어진 입력들이 먼저 

N이 주어지는데 이건 큐 또는 스택의 갯수를 말하는 것이고

다음 2번째 줄은 각각의 큐 또는 스택을 결정하는 명령어였다. 0이면 큐이고 1이면 스택이다

다음 줄은 각각의 큐 또는 스택에 들어갈 값이였다

그후 수열의 크기 M이 주어지고 

다음 줄에 수열의 원소들이 주어지게 되는 것이다

 

이 것을 이해하기 까지 좀 걸렸다...

 

문제 설명이랑 입력값과 출력 값을 비교하여 왜 저렇게 되지 하면서 계속 고민만 하다가 입력에 대한 설명을 다시 차근히 읽고 난뒤에야 이해가 되었다

 

문제를 이해하고 생각보다 코드를 빠르게 쓸 수 있었다(복선인가...)

 

실패코드

import sys
from collections import deque

N = int(sys.stdin.readline().strip())
queuestack = []
for a, b in zip(list(map(int, sys.stdin.readline().split())), list(map(int, sys.stdin.readline().split()))):
    if a == 0:
        queuestack.append(deque([b]))
    else:
        queuestack.append([b])
M = int(sys.stdin.readline().strip())
C = list(map(int, sys.stdin.readline().split()))
answer = []
for x in C:
    add_x = x
    for check in queuestack:
        check.append(add_x)
        if str(type(check)) == "<class 'list'>":
            add_x = check.pop()
        else:
            add_x = check.popleft()
    answer.append(add_x)

sys.stdout.write(f'{" ".join(map(str, answer))}')

의식의 흐름대로 입력에 대한 설명 + 문제 설명의 로직대로 코드를 제출을 하였지만 시간초가나면서 실패하게 되었다.

일단 for문이 2개이기에 이것의 시간 복잡도는 O(N^2)이다

 

그럼 최소 O(N)으로 바꿔야지만 통과가 된다는 의미이기도 하다

그럼 일단 필요없는 스택 - 삽입 후 출력하기에 결국 삽입한 값이 나오기에 스택은 불필요하다는 것을 알 수 있다. 그렇기에 불필요한 스택에 대한 정보는 삭제 처리하였지만 그래도 시간초가 난다...

 

그러다가 생각해보니깐 결국은 먼저 하나의 큐에 값을 앞에서부터 넣으면 된다는 것을 알게 되었다

왜냐하면 1,2,3을 문제의 설명되로 한다고 했을 때 3이 나오게 하면(큐 기준) 되는 것이다 만약 스택으로만 이루어졌다고 하면 입력받은 순서대로 뽑아내면 되는 것이다

 

정답 주의

import sys
from collections import deque

N = int(sys.stdin.readline().strip())
que = deque([])
for a, b in zip(list(map(int, sys.stdin.readline().split())), list(map(int, sys.stdin.readline().split()))):
    if a == 0:
        que.appendleft(b)

M = int(sys.stdin.readline().strip())
C = list(map(int, sys.stdin.readline().split()))
answer = []
for x in C:
    que.append(x)
    answer.append(que.popleft())

sys.stdout.write(f'{" ".join(map(str, answer))}')