๐ ์ถ์ฒ - 10845 - ํ
๋ฌธ์ ์ค๋ช
์ ์๋ฅผ ์ ์ฅํ๋ ํ๋ฅผ ๊ตฌํํ ๋ค์, ์
๋ ฅ์ผ๋ก ์ฃผ์ด์ง๋ ๋ช
๋ น์ ์ฒ๋ฆฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
๋ช ๋ น์ ์ด ์ฌ์ฏ ๊ฐ์ง์ด๋ค.
์
๋ ฅ
์ฒซ์งธ ์ค์ ์ฃผ์ด์ง๋ ๋ช
๋ น์ ์ N (1 โค N โค 10,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๋ช
๋ น์ด ํ๋์ฉ ์ฃผ์ด์ง๋ค. ์ฃผ์ด์ง๋ ์ ์๋ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ๋ค. ๋ฌธ์ ์ ๋์์์ง ์์ ๋ช
๋ น์ด ์ฃผ์ด์ง๋ ๊ฒฝ์ฐ๋ ์๋ค.
์ถ๋ ฅ
์ถ๋ ฅํด์ผํ๋ ๋ช
๋ น์ด ์ฃผ์ด์ง ๋๋ง๋ค, ํ ์ค์ ํ๋์ฉ ์ถ๋ ฅํ๋ค.
์ ์ถ๋ ฅ ์
์์ ์ ๋ ฅ | ์์ ์ถ๋ ฅ | |
---|---|---|
-- | 15 push 1 push 2 front back size empty pop pop pop size empty pop push 3 empty front | 1 2 2 0 1 2 -1 0 1 -1 0 3 |
๋ฌธ์ ์ ์ฃผ์ด์ง ๊ทธ๋๋ก ๊ตฌํํ๋ฉด ๋๋ค.
์ฌ๊ธฐ์push
๋ฅผ ์ ์ธํ ๋๋จธ์ง ๋จ์ด๋ ํ ๋จ์ด์ด๊ธฐ ๋๋ฌธ์ ๊ทธ๋๋ก ๊ตฌํํ๋ฉด ๋์ง๋ง,push
์ ๊ฐ์ ๊ฒฝ์ฐex) push 1
๊ณผ ๊ฐ์ด ๋์ด ์์ด ์ซ์๋ฅผ ๋ผ์ด๋ด์ผ ํ๋ค๋ ์ ๋ง ์ ์ํ๋ฉด ์ด๋ฒ ๋ฌธ์ ๋ ์ฝ๊ฒ ํด๊ฒฐํ ์ ์๋ค.
from queue import deque
import sys
queue = deque()
input = sys.stdin.readline
def check(queue, word):
if word[0] == 'front':
if len(queue) != 0:
print(queue[0])
else:
print(-1)
elif word[0] == 'back':
if len(queue) != 0:
print(queue[-1])
else:
print(-1)
elif word[0] == 'size':
print(len(queue))
elif word[0] == 'empty':
if len(queue) == 0:
print(1)
else:
print(0)
elif word[0] == 'pop':
if len(queue) > 0:
print(queue.popleft())
else:
print(-1)
else:
queue.append(int(word[1]))
N = int(input())
for i in range(N):
word = input().split()
check(queue, word)
Deque(๋ฐํฌ)๋ double-ended queue ์ ์ค์๋ง๋ก, ์๊ณผ ๋ค์์ ์ฆ, ์๋ฐฉํฅ์์ ๋ฐ์ดํฐ๋ฅผ ์ฒ๋ฆฌํ ์ ์๋ queueํ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์๋ฏธํ๋ค. ์๋์ ๊ทธ๋ฆผ์ deque์ ๊ตฌ์กฐ๋ฅผ ๋ํ๋ธ ๊ทธ๋ฆผ์ด๋ค.
python์์ collections.deque
๋ list
์ ๋น์ทํ๋ค. list
์ append()
, pop()
๋ฑ์ ๋ฉ์๋๋ฅผ deque
์์๋ ์ ๊ณตํ๋ค. ์์ ์์ค์ฝ๋๋ค์ ํตํด list
์ deque
์ ์ฐจ์ด๋ฅผ ์์๋ณด๋๋ก ํ์. collections.deque
์ ์์ธํ ์ค๋ช
์ docs.python.org์์ ํ์ธํ ์ ์๋ค.
collections.deque
์ ๋ฉ์๋๋ค ์ค list
์ ์ฐจ์ด๋ฅผ ๋ณด์ด๋ ๋ฉ์๋๋ค ์์ฃผ๋ก ์ดํด ๋ณด๋๋ก ํ๋ค. ์ ์ฒด ๋ฉ์๋๋ค์ docs.python.org์์ ํ์ธํ ์ ์๋ค.
list.append(x)
์ ๋ง์ฐฌ๊ฐ์ง๋ก x
๋ฅผ deque
์ ์ค๋ฅธ์ชฝ(๋ง์ง๋ง)์ ์ถ๊ฐ(์ฝ์
)ํด์ค๋ค.
์์์ ์ค๋ช
ํ๋ค์ํผ, deque
๋ ์๋ฐฉํฅ์์ ๋ฐ์ดํฐ๋ฅผ ์ฒ๋ฆฌํ ์ ์๋ ๊ตฌ์กฐ์ด๋ค. ๋ฐ๋ผ์, append(x)
๊ฐ ์ค๋ฅธ์ชฝ์์ ์ถ๊ฐ(์ฝ์
)์ ํด์ค๋ค๋ฉด, appendleft(x)
๋ ์ผ์ชฝ ์ฆ, ์์ชฝ์์ x๋ฅผ ์ถ๊ฐ(์ฝ์
)ํด์ฃผ๋ ๋ฉ์๋์ด๋ค.
list.extend(iterable)
๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก iterable argument(list, str, tuple...)
๋ฅผ ์ค๋ฅธ์ชฝ(๋ง์ง๋ง)์ elements๋ฅผ ์ถ๊ฐ(์ฝ์
)ํด์ฃผ๋ ๋ฉ์๋์ด๋ค. (iterable argument ๋ arguments์ ๊ฐ ์์๋ฅผ ํ๋์ฉ ๋ฐํ ๊ฐ๋ฅํ object๋ฅผ ์๋ฏธํ๋ค.) [์์ 3-2]๋ append vs extend
์ ์ฐจ์ด๋ฅผ ๋ํ๋ธ ์์ ์ด๋ค.
collections.deque.extendleft()
๋ appendleft()
์ ๋ง์ฐฌ๊ฐ์ง๋ก ์ผ์ชฝ(์์ชฝ)์์ ๋ฐ์ดํฐ๋ฅผ ์ถ๊ฐํด์ฃผ๋ ๋ฉ์๋์ด๋ค.
list.pop()
๊ณผ ๊ฐ์ด ์ค๋ฅธ์ชฝ(๋ง์ง๋ง)์์ ๋ถํฐ ์ฐจ๋ก๋๋ก ์ ๊ฑฐ์ ๋ฐํ(remove and return)์ ํ๋ ๋ฉ์๋์ด๋ค.
pop()
์ ๋ฐ๋๋ก, ์ผ์ชฝ(์์ชฝ)์์ ๋ถํฐ ์ฐจ๋ก๋๋ก ์ ๊ฑฐ์ ๋ฐํ(remove and return)์ ํ๋ ๋ฉ์๋์ด๋ค.
collections.deque.rotate(n)
์ ์์๋ค(elements)์ n๊ฐ ๋งํผ ํ์ ํด์ฃผ๋ ๋ฉ์๋์ด๋ค. n์ ๊ฐ์ด ์์(negative)์ด๋ฉด ์ผ์ชฝ์ผ๋ก ํ์ ํ๊ณ , n์ ๊ฐ์ด ์์์ด๋ฉด ์ค๋ฅธ์ชฝ์ผ๋ก ํ์ ํ๋ค.