#13 [파이썬] 백준 18115번 : 카드 놓기

<문제>

www.acmicpc.net/problem/18115

18115번: 카드 놓기

---

 

<소스코드>

import sys
from collections import deque

n = int(input())
deq = deque()
result = deque(range(1, n+1))

skill = list(sys.stdin.readline().split())

for i in reversed(skill):
    p = result.popleft()
    if i == '1':
        deq.appendleft(p)
    elif i == '2':
        deq.insert(1, p)
    else:
        deq.append(p)

print(*deq)

 

특정 규칙대로 순차적으로 적용했을 때 마지막에 적용한 것 것부터 규칙에 맞춰 복구하면 원상태의 배열을 알 수 있다.

---

 

<NOTE>

1. 덱(deque)이란?

큐(que)는 먼저 저장된 것이 먼저 나오는 FIFO(First In First Out)구조를 가지며, 스택(stack)은 나중에 저장된 것이 먼저 나오는 LIFO(Last In First Out)구조를 가진다. 덱(deque)은 Double Ended Queue의 약자로 스택과 큐의 작동을 모두하여 양방향으로 삽입과 삭제가 가능한 구조를 가진다. 

 

2. deque의 삽입/삭제 시간 복잡도

l[i] = x또는 del l[i]과 같은 리스트 삽입/삭제 연산은 시간 복잡도가 O(N)이다. 반면 deque를 사용하여 양쪽에 append 또는 pop을 할 경우 O(1)의 시간 복잡도를 가지므로 훨씬 빠르게 수행할 수 있다. 즉, 값을 넣고 뺄때는 deque가 list보다 더 뛰어나다.

 

3. deque의 메서드(method)

· item을 덱 오른쪽 끝에 삽입: append(item)

deq = deque()
deq.append(item)

· item을 덱 왼쪽 끝에 삽입: appendleft(item)

deq = deque()
deq.appendleft(item)

· 덱의 오른쪽 끝 item을 가져오고 덱에서 삭제: pop()

deq = deque()
deq.pop()

· 덱의 왼쪽 끝 item을 가져오고 덱에서 삭제: popleft()

deq = deque()
deq.popleft()

· 덱에서 특정 item을 찾아 삭제: remove(item)

deq = deque()
deq.remove(item)

· 덱의 요소들을 num만큼 회전(num이 양수이면 우로 이동, 음수이면 좌로 이동): rotate(num)

deq = deque([1, 2, 3, 4])
deq.rotate(1)
print(deq) #deque([4, 1, 2, 3])

deq.rotate(-1)
print(deq) #deque([1, 2, 3, 4])

· 덱의 특정 index에 item 삽입: insert(index, item)

deq = deque(['사과'])

deq.insert(1, '바나나')

print(*deq) #사과 바나나

 

4. 리스트의 거꾸로 반복문

리스트 내의 요소를 역순으로 반복하고자 할 때: for i in reversed(리스트)

lst = [1, 2, 3, 4, 5]
for i in reversed(lst):
	print(i, end=' ') #5, 4, 3, 2, 1

 

5. item을 덱의 왼쪽 끝에서 가져와 사용 후 제거: a = deq.popleft()

from collections import deque

deq1 = deque([1, 2, 3])
deq2 = deque([4])

a = deq1.popleft()
deq2.appendleft(a)

print(*deq1) #2 3
print(*deq2) #1 4

deq1.popleft()를 a라는 새로운 변수에 저장하여 item을 사용하고 지우는 것을 한 번에 적용할 수 있다.

 

6. container내의 요소만 띄어쓰기로 구분하여 출력: print(*deq)

deq = deque([1, 2, 3, 4])
print(deq) #deque([1, 2, 3, 4])
print(*deq) #1 2 3 4

lst = ['수박', '딸기', '메론', '감']
print(lst) #lst = ['수박', '딸기', '메론', '감']
print(*lst) #수박 딸기 메론 감

반복문을 사용하여 리스트의 요소를 하나하나 출력하는 것 보다 훨씬 간결하다.