백준 24511 [python]

1차 시도 - 실패

from collections import deque
import sys

N = int(sys.stdin.readline().rstrip())

# 스택 혹은 큐이므로 dequeue를 사용한다. 
dequeue = deque([deque() for i in range(N)])

# 스택인지 큐인지 
typeList = list(map(int, sys.stdin.readline().split()))

# 각 자료구조에 어떤 원소가 들어있는지 
dataList = list(map(int, sys.stdin.readline().split()))

# 넣을 때는 큐나 스택이나 뒤로 들어가기 때문에 조건 검사 필요 없음 
for i in range(N) :
    dequeue[i].append(dataList[i])

# 수열의 길이가 주어진다. 
M = int(sys.stdin.readline().rstrip())
numList = list(map(int, sys.stdin.readline().split()))

def queuestack(N, dequeue, typeList, temp) :
    for i in range(N) :
        # n-1번째 자료구조에 삽입 
        dequeue[i].append(temp)

        # n번째 자료구조에 삽입할 xn-1을 꺼내는 작업 
        if typeList[i] == 0 :
            temp = dequeue[i].popleft()
        else :
            temp = dequeue[i].pop()
    return temp 

for z in range(M) :
    print(queuestack(N, dequeue, typeList, numList[z]), end=" ")

풀이

1. 2차원 deque를 선언한다.
2. 2차원 deque에 데이터를 삽입한다.
3. 각 수열을 삽입하고 결과를 뱉는 함수를 구현할 때, 
   typeList에 적혀있는대로 자료구조에 맞게 append하고 pop하는 과정을 수행한다.
4. 결과를 낸다. 

결과

O(N^2)의 시간복잡도를 가지고 있으므로 입력의 개수를 고려했을 때, 반드시 시간초과가 발생한다. 

2차 시도

from collections import deque
import sys

N = int(sys.stdin.readline().rstrip())

# 스택 혹은 큐이므로 dequeue를 사용한다. 
dequeue = deque()

# 스택인지 큐인지 
typeList = list(map(int, sys.stdin.readline().split()))

# 각 자료구조에 어떤 원소가 들어있는지 
dataList = list(map(int, sys.stdin.readline().split()))

# 넣을 때는 큐나 스택이나 뒤로 들어가기 때문에 조건 검사 필요 없음 
for i in range(N) :
    if typeList[i] == 0 :
        dequeue.append(dataList[i])

# 수열의 길이가 주어진다. 
M = int(sys.stdin.readline().rstrip())
numList = list(map(int, sys.stdin.readline().split()))

for i in numList :
    dequeue.appendleft(i)
    print(dequeue.pop(), end=" ")

풀이

스택과 큐 개념을 적용하여 풀 수 있는 문제다.
각 자료구조에서 데이터를 넣고 빼는 과정에서 스택의 경우 들어온 값이 바로 나가므로 자료구조를 유지할 필요가 없다.
반면 큐의 경우 가장 먼저 들어온 데이터를 꺼내기 때문에 자료구조를 유지해야하고, 여러 개의 큐가 하나의 큐처럼 동작하는 것을 알 수 있다. 

1. 자료구조에 원소를 삽입할 때, 저장되는 자료구조가 큐라면 하나의 큐에 원소를 저장한다.
2. 각 수열 원소를 삽입하는 반복문을 수행하면서, 큐에서 하나의 원소를 pop하여 출력하면 된다.

결과

배운점

사실 지금까지 시간 복잡도를 전혀 고려하지 않고 풀었다. 시간초과가 발생하면 
그 때 가서 시간초과를 해결하기 위해서 내가 작성한 코드 내에서 문제를 해결하려고 했다. 
그러다보니 시야가 좁아져 다른 방법을 전혀 생각해낼 수 없없다. 
-> 작성한 코드 내에서 해결하려다 보니 스택과 힙 사이의 관계를 전혀 활용할 수 없었음 
-> 혼자 힘으로 이 문제를 못풀게 됨 

앞으로는 문제를 읽고 어떤 방식으로 이 시간을 해결할지 고민 먼저 해봐야겠다.
또한 어떤 식으로 문제를 해결해야할지 모르겠을 때는 그림으로 그려봐야겠다.