[백준/Python] 24511 queuestack

문제: https://www.acmicpc.net/problem/24511

 

 

사용 알고리즘: 큐, 스택 

 

 

입력

• 첫째 줄에 queuestack 을 구성하는 자료구조의 개수 N (1 <= N <= 100,000)
• 둘째 줄에 길이 N 의 수열 A -> Ai = 0 이면 큐, Ai = 1 이면 스택
• 셋째 줄에 길이 N 의 수열 B, 자료구조에 들어있는 원소 (1 <= Bi <= 1,000,000,000)
• 넷째 줄에 삽입할 수열의 길이 M (1 <= M <= 100,000)
• 다섯째 줄에 queuestack 에 삽입할 원소를 담고 있는 길이 M 의 수열 C (1 <= 1,000,000,000)

 

일단 첫번째 시도는 시간초과로 1% 에서 바로 컷당했다.

문제에서 주어진 그대로를 구현하면 바로 시간 초과가 뜬다. 틀린 코드부터 먼저 보자.

 

틀린 코드

import sys
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()))

def queueStack(qs, d, arr): # (큐or스택, 덱, 숫자 배열)
    result = []
    if qs == 0: # 큐
        for i in range(M):
            d.append(arr[i])
            result.append(d.popleft())
    else: # 스택
        for i in range(M):
            d.append(arr[i])
            result.append(d.pop())
    return result

inputArr = C
for i in range(N):
    if A[i] == 0: # 큐
        q = deque()
        q.append(B[i])
        inputArr = queueStack(0, q, inputArr)
    else: # 스택
        s = deque()
        s.append(B[i])
        inputArr = queueStack(1, s, inputArr)

for i in range(len(inputArr)):
    print(inputArr[i], end = ' ')

 

큐스택을 구성하는 큐와 스택은 최대 100,000 개인데, 모든 큐와 스택을 만들자니 메모리 낭비가 너무 심하다고 생각했다.

그래서 i 번째 자료구조에 넣어야할 숫자를 차례로 넣고 차례로 빼서 배열을 만들고 그 배열을 다음 자료구조에 차례로 넣고 차례로 빼는 방식으로 구현을 했다. 숫자를 차례로 넣고 차례로 빼는 과정은 queueStack 이라는 함수를 만들어서 처리했다. 

 

하지만, 시간초과

코드를 대충 봐도 알겠지만, O(n^2) 의 시간 복잡도를 가진다.

문제에서 주어진 시간제한은 1초이고, 자료구조의 최대 개수는 100,000 개이다.

 

컴퓨터가 1초에 계산할 수 있는 연산은 대략 1억번인데, N 의 최대값이 10만이니 계산해보면 100억이 된다. 시간초과가 날 수 밖에..

-> 100,000 * 100,000 = 10,000,000,000 

 

 

시간을 어떻게 줄여야하나 고민을 했는데, 생각보다 간단한 방법으로 시간을 줄 일 수 있었다. 큐와 스택의 특성를 생각해보자.

• 큐 -> FIFO 먼저들어간 놈이 먼저 나옴
• 스택 -> LIFO 나중에 들어간 놈이 먼저 나옴

i 번째 자료구조가 스택이고, 스택에 1이라는 숫자가 들어있다고 가정해보자. 그리고 차례로 2, 3, 4 가 스택에 들어온다고 생각해보자. 

 

초기 상태: [1]

2 들어옴: [1, 2] 

pop: [1, 2]

3 들어옴: [1, 3]

pop: [1, 3]

4 들어옴: [1, 4]

pop: [1, 4]

최종 상태: [1]

 

스택은 나중에 들어온 놈이 먼저 나간다. 어떤 수를 집어넣고 pop 하면 방금 들어왔던 수가 pop 된다. 

-> 즉, i 번째 자료구조가 스택이라면 들어온대로 나갈테니 그냥 무시

 

 

스택은 무시하면 되니 이제 큐는 어떻게 처리해야할지 생각해보자. 아래의 그림은 큐에서 큐로 숫자가 이동하는 상황이다. 

코드의 효율을 위해 숫자를 하나 넣고 하나 pop 하지 않고 한번에 넣고 한번에 pop 하는 상황을 가정하고 그려보았다. 

 

다음 큐로 이동하는 숫자 배열은

들어온 숫자 배열 0번째 인덱스에 큐에 원래 들어있던 값을 추가하고, 

들어온 숫자 배열의 맨 끝에 있는 숫자를 제거한 배열이다.

 

이걸 이용하면 매번 2*M회의 append-pop 을 할 필요없이, 1번의 append 와 1번의 pop 만 하면 된다. 

 

 

 

그럼 이제 통과한 코드를 살펴보자.

 

 

삽입할 수열 C 는 리스트가 아니라 덱으로 만들어서 수열을 넣었다. 

위의 그림을 보면 알겠지만, 다음 큐로 넘어갈 수열은 기존에 삽입된 수열의 맨 앞에 숫자를 추가해야 한다. 리스트를 사용하면 맨 앞에 숫자를 추가할 때 현재 리스트에 들어있는 요소의 길이만큼의 이동이 필요하다. (리스트에 n 개의 요소가 있다면 O(n) 시간이 걸리는 셈)

 

그러므로 앞뒤로 요소를 추가/제거 할 수 있는 덱을 사용했다. (덱은 앞에 원소를 추가해도 연산시간이 O(1) 밖에 걸리지 않는다)

# 입력
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
M = int(input())
C = deque(map(int, input().split())) // 리스트가 아닌 덱으로

 

 

for 문을 돌면서 기존 배열에

• 큐에 있던 원소를 기존 배열 앞에 추가
• 기존 배열의 마지막 원소를 제거

하면서 다음 큐로 넘어갈 배열을 만들어줬다. 

for i in range(N):
    if A[i] == 0:
        C.appendleft(B[i]) # 삽입된 배열의 앞에 큐에 있던 원소 추가
        C.pop() # 삽입된 배열의 마지막 원소 제거

# 출력
for i in range(len(C)):
    print(C[i], end = ' ')

 

 

 

전체 코드

import sys
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 = deque(map(int, input().split()))

for i in range(N):
    if A[i] == 0:
        C.appendleft(B[i]) # 삽입된 배열의 앞에 큐에 있던 원소 추가
        C.pop() # 삽입된 배열의 마지막 원소 제거

# 출력
for i in range(len(C)):
    print(C[i], end = ' ')

 

 

 

시간 복잡도

 

- 입력

 

입력의 총 시간 복잡도는 O(n) 이다.

수열의 길이가 가장 길 때의 값이 입력의 총 시간 복잡도가 될 텐데, N 과 M 의 최대값은 모두 100,000 으로 같다.

그래서 O(m) = O(n) 시간이다. (편의상 O(N), O(M) 이라고 안하고 O(n), O(m) 이라고 썼음)

N = int(input()) # O(1)
A = list(map(int, input().split())) # O(수열 A의 길이)
B = list(map(int, input().split())) # O(수열 B의 길이)
M = int(input()) # O(1)
C = deque(map(int, input().split())) # O(수열 M의 길이)

# O(n)

 

연산

• appendleft / pop: O(1)

O(n) = O(m) 이므로 O(n) 

for i in range(N): # O(n)
    if A[i] == 0:
        C.appendleft(B[i]) 
        C.pop() 

for i in range(len(C)): # O(m)
    print(C[i], end = ' ')
    
# O(n)

 

 

그래서 총 시간 복잡도를 구해보면, O(n) + O(n) = O(2n) = O(n)