[Silver III] 카드 놓기 - 18115 (python)

문제 링크

 

 

분류

자료 구조, 덱

 

문제 설명

수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다.

1. 제일 위의 카드 1장을 바닥에 내려놓는다.
2. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.
3. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.

수현이는 처음에 카드 N장을 들고 있다. 카드에는 1부터 N까지의 정수가 중복되지 않게 적혀 있다. 기술을 N번 사용하여 카드를 다 내려놓았을 때, 놓여 있는 카드들을 확인했더니 위에서부터 순서대로 1, 2, …, N이 적혀 있었다!

놀란 수현이는 처음에 카드가 어떻게 배치되어 있었는지 궁금해졌다. 처음 카드의 상태를 출력하여라.

입력

첫 번째 줄에는 N (1 ≤ N ≤ 106)이 주어진다.

두 번째 줄에는 길이가 N인 수열 A가 주어진다. Ai가 x이면, i번째로 카드를 내려놓을 때 x번 기술을 썼다는 뜻이다. Ai는 1, 2, 3 중 하나이며, An은 항상 1이다.

출력

초기 카드의 상태를 위에서부터 순서대로 출력하여라.

 

코드

 

1. 시간초과

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
stack = []

for i in range(n-1, -1, -1):
    num = n-i

    if arr[i] == 1:
        stack = [num] + stack
    elif arr[i] == 2:
        stack.insert(1, num)
    else:
        stack.append(num)

print(stack)

 

2. 성공

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

n = int(input())
arr = list(map(int, input().split()))
q = deque()

for i in range(n-1, -1, -1):
    num = n-i

    if arr[i] == 1:
        q.appendleft(num)
    elif arr[i] == 2:
        q.insert(1, num)
    else:
        q.append(num)

print(*q)

 

1. 시간초과 문제

stack = [num] + stack 연산은 num이 포함된 리스트를 기존의 stack 리스트와 연결합니다.

이는 새로운 리스트를 만들기 위해 모든 요소를 복사해야 하므로 시간 복잡도가 O(n)이 되지만

 

2번째 deque을 사용하여 q.appendleft 를 할 경우 시간복잡도는 O(1)이 됩니다.