[백준/Python] 18115번 - 카드 놓기

문제

백준 18115번 - 카드 놓기

해결 과정

• 삽입,삭제가 양쪽으로 가능한 queue 이용
• 기술 번호는 오른쪽에서부터 pop
• 바닥에 놓여있는 카드 번호는 왼쪽에서부터 popleft
• 기술 번호에 맞춰서 원래 자리로 놓기
  • 1번: 제일 위로 = 제일 앞으로 = appendleft
  • 2번: 위에서 두번째로 = 인덱스 1 = insert(1,~)
  • 3번: 제일 밑으로 = 제일 뒤로 = append

시행착오

• 어려운 구현은 아니었는데 이해하는데 시간이 걸렸다..
• 바닥에 내려놓은 카드 리스트는 맨 뒤(밑)에서부터 빼서 해당 기술의 번호를 보고 그 카드의 원래 자리로 되돌려 놓는 것으로 구현

append와 insert의 시간 차이

• append 시간 복잡도: O(1)
• insert 시간 복잡도: O(N)
• append가 insert보다 빠르다!

  https://wayhome25.github.io/python/2017/06/14/time-complexity/

풀이

import sys
from collections import deque

n = int(sys.stdin.readline())

# 기술 번호
tech = list(map(int,sys.stdin.readline().split()))
# 바닥에 내려놓은 카드 (1,2,3,4,5)
card = deque(range(1,n+1))
# 초기 카드의 상태
origin = deque()

while card:
  t = tech.pop()
  c = card.popleft()
  if t == 1:
    origin.appendleft(c)
  if t == 2:
    origin.insert(1,c)
  if t == 3:
    origin.append(c)

print(*origin)