#백준 11866
1. 처음에 문제를 읽고 원형linked list를 떠올렸다.
2. 아직 linked list는 익숙하지가 않아서 구글링을 하던중 deque를 사용하는 사람들이 대다수였다.
from collections import deque
n, k = map(int,input().split())
deq = deque([])
for i in range(1, n + 1):
deq.append(i)
print('<', end='')
while len(deq) >0:
deq.rotate(-k)
if len(deq) == 1:
print('{}>'.format(deq.pop()))
else:
print('{},'.format(deq.pop()), end=' ')
- 이건 내가 작성한 코드( deque의 rotate사용, 92ms)
- append로 사용하면 이중 반복문이 되면서 시간이 늘어났다!
- 틀렸습니다는 print( end = ' ')에서 공백없이 따옴표 쓰는 바람에...ㅠ^ㅠ
3. deque란?
- 양방향 queue로 맨 앞, 뒤 element의 pop, append에 최적화 되어있다.
- deque는 구현에따라 stack으로도 queue로도 사용할 수 있어서, push/pop 연산이 많은 문제에서 유용하다
4. deque의 method
- deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.
- deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.
- deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
- deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
- deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.
- deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.
- deque.remove(item): item을 데크에서 찾아 삭제한다.
- deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).
출처 : https://leonkong.cc/posts/python-deque.html
5. deque 구현
from collections import deque
deq = deque([1,2,3,4,5])
deq.append(6)
# deq = deque([1, 2, 3, 4, 5, 6])
deq.appendleft(0)
# deq = deque([0, 1, 2, 3, 4, 5, 6])
deq.pop()
# 실행결과 6
deq.popleft()
# 실행결과 0
deq = deque([1,2,3,4])
arr = [5,6]
deq.extend(arr)
# deq = deque([1, 2, 3, 4, 5, 6])
deq.extendleft(arr)
# deq = deque([6, 5, 1, 2, 3, 4])
deq.remove(6)
# deq = deque([5, 1, 2, 3, 4])
deq.rotate(-2)
# deq = deque([2, 3, 4, 5, 1])
# 앞의 숫자가 맨 뒤로 이동X2 or 왼쪽으로 두번 이동
deq.rotate(1)
# deq = deque([1, 2, 3, 4, 5])
# 뒤의 숫자가 맨 앞으로 이동 or 오른쪽으로 한번 이동※ deq.extend와 deq.extendleft는 따로 실행했다고 생각해주세요^~^
반응형