20단계 문제들 : 큐, 덱
인트로
fron collections import deque
큐
python에서는 큐를 리스트와 queue 라이브러리를 이용하면 구현할 수 있다.
덱 (deque)
queue는 선입선출 방식이다.
deque은 양방향 큐라고 볼 수 있다. 앞, 뒤 양 방향으로 요소를 추가하거나 제거할 수 있다.
list에 비해 양방향 요소에 접근하는 방법이 O(1)로 매우 빠르다. (일반적인 리스트는 O(n))
덱의 메소드들
- 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://chaewonkong.github.io/posts/python-deque.html
18258번 - 큐 2
스택이나 큐의 기능을 기본적으로 학습할 때에 나오는 문제이다.
명령어에 대해 큐에서의 메소드를 구현하면 된다.
코드
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
A = deque()
for _ in range(N):
mode = input()
if 'push' in mode:
modes, x = mode.split()
A.append(x)
if 'front' in mode:
if len(A) !=0:
front = A[0]
print(front)
else:
print(-1)
if 'back' in mode:
if len(A) !=0:
back = A[-1]
print(back)
else:
print(-1)
if 'empty' in mode:
if len(A) !=0:
print(0)
else:
print(1)
if 'size' in mode:
print(len(A))
if 'pop' in mode:
if len(A) !=0:
a = A.popleft()
print(a)
else:
print(-1) queue는 리스트로 만드는 방법도 있지만 시간복잡도 측면에서 deque를 만드는 것이
양 방향의 끝 원소를 접근하는 것이 O(1)로 시간복잡도가 가장 짧기 때문에 deque를 이용하는 것이 맞다.
리스트로 구현하면 시간초과가 나는 것 같다.
2164번 - 카드 2
카드 게임을 구현하면 된다.
N이 주어졌을 때 순서대로 맨 위를 버리고, 그 다음 것을 맨 뒤로 보내고 ...를 반복 했을 때
맨 마지막에 남는 카드를 구하는 것이다.
코드
from collections import deque
myque = deque()
N = int(input())
for i in range(1,N+1):
myque.append(i)
while (len(myque)>1):
myque.popleft()
myque.append(myque.popleft())
print(myque[0])큐가 하나 남을 때까지 반복한 다음 마지막 남은 큐의 값을 출력하면 된다.
11866번 - 요세푸스 문제 0
리스트로 사용했던 저번 문제와 동일하다.
위가 deque로 구현했고 아래가 list로 구현했는데 시간이나 메모리가 list가 더 빨랐다.
import sys
input = sys.stdin.readline
from collections import deque
n, k = map(int, input().split())
numbers = deque(range(1, n+1))
result = []
while numbers:
for _ in range(k-1):
numbers.append(numbers.popleft())
result.append(str(numbers.popleft()))
print('<' + ', '.join(result) + '>')이 문제는 리스트를 이용하는게 ..
popleft()를 n-1번씩 반복해야돼서 더 느린 거 같다.
1966번 - 프린터 큐
Queue 자료구조를 따르는 프린터기이며, 이 조건에 따라 몇 번째로 인쇄되는지 출력하면 된다.
코드 리뷰
import sys
input = sys.stdin.readline
test_cases = int(input())
for i in range(test_cases):
n, m = map(int, input().split())
queue = list(map(int, input().split()))
queue = [(j, idx) for idx, j in enumerate(queue)]
count = 0
while True:
if queue[0][0] == max(queue, key=lambda x:x[0])[0]: ##x[0]이 중요도!
count += 1
if queue[0][1] == m: #중요도가 가장 크고, 궁금한 index 였으면 count 출력
print(count)
break
else:
queue.pop(0)
else:
queue.append(queue.pop(0))사실 나는 우선순위에 대한 것을 먼저 생각해서 수학적으로 다가갔다.
Queue에 대한 것보단 수학적으로 다가가는 방법이 있을 것이라고 생각했다.
그러다보니 좀 많은 예외상황 ..^^ 들이 생겨서 gpt에게 도움을 요쳥했다.
enuermate()
파이썬의 내장함수로 인덱스와 원소를 동시 접근하면서 루프를 돌리게 도와준다.
>>> for A in enumerate(['A','B','C']):
print(A)
(0,'A')
(1,'B')
(2,'C')의 결과를 얻게 된다.
알아서 튜플 형태로 나오기 때문에 각각 다른 변수로 할당 받고 싶다면 인자 풀기를 하면 된다.
iter ( 호출 가능한 객체, 반복 끝낼 값 )
반복을 끝낼 값 ( = 감시자) 을 지정하면 특정 값이 나올 때 반복을 끝낸다.
next ()
iter와 같이 쓰인다.
>>> x = ['mary', 'is', 'find']
>>> x = next(iter_x)
>>> x
'mary'
>>> x = next(iter_x)
>>> x
'is'
>>> x = next(iter_x)
>>> x
'find'lambda
lambda 인자 : 표현식
ex) lambda x : x*2
1) map 함수와의 응용
map (함수, 리스트/튜플)
map 함수와 함께 쓰이면 이런 예제를 가질 수 있다.
result = list(map(lambda x: x+2), [1,2,3,4,5])
>>>result
[3,4,5,6,7]filter (함수, 리스트/튜플)
filter 함수와 함께 쓰이면 이런 예제를 가질 수 있다.
>>> a = [1,3,5,6,7]
>>> list(filter(lambda x: x%2 != 0, a))
[6]이런식으로 filter의 함수 부분의 lambda 를 이용해서 표현식을 만들어줄 수 있다.
10866번 - 덱
덱의 기능을 구현하는 것이다.
코드
import sys
input = sys.stdin.readline
from collections import deque
T = int(input())
myqueue = deque()
for i in range(T):
string = str(input()).strip()
if 'push_front' in string:
mode, x = string.split()
myqueue.appendleft(x)
if 'push_back' in string:
mode, x = string.split()
myqueue.append(x)
if 'pop_front' == string:
if myqueue:
print(myqueue.popleft())
else:
print(-1)
if 'pop_back' == string:
if myqueue:
print(myqueue.pop())
else:
print(-1)
if 'size' == string:
print(len(myqueue))
if 'empty' == string:
if myqueue:
print('0')
else:
print('1')
if 'front' == string:
if myqueue:
print(myqueue[0])
else:
print(-1)
if 'back' == string:
if myqueue:
print(myqueue[-1])
else:
print(-1)back이라는 단어가 push_back과 back에 둘 다 있기 때문에 문자열 처리 하는 부분을 조심해야 된다.
그 외에는 그냥 평이한 기능 구현.
1021번 - 회전하는 큐
N의 원소를 포함한 양 방향 순환 큐가 있다고 가정한다.
지민이는 총 3개의 연산을 할 수 있다.
첫 번째 원소 뽑아내기, 왼쪽으로 전체 이동, 오른쪽으로 전체 이동
전체적인 연산을 가장 적게할 수 있는 경우의 수를 출력하면 된다.
코드
import sys
input = sys.stdin.readline
from collections import deque
myqueue = deque()
N, M = map(int,input().split())
for i in range(1,N+1):
myqueue.append(i)
order = list(map(int,input().split()))
count = 0
for i in order:
while (True):
length = len(myqueue)
disctance = myqueue.index(i)
if disctance > length // 2:
flag = 0 #뒤에서 꺼내기
else:
flag = 1 #앞에서 꺼내기
if myqueue[0] == i:
myqueue.popleft()
break
if flag:
myqueue.append(myqueue.popleft())
else:
myqueue.appendleft(myqueue.pop())
count += 1
print(count)연산 부분은 왼쪽에서 뽑아서 맨 오른쪽에 붙이기, 맨 오른쪽에서 뽑아서 맨 왼쪽에 붙이기 등으로
구현하기 편리하다.
하지만, 최소 연산이라는 조건이 있기 때문에 왼쪽에서 뽑을지, 오른쪽에서 뽑을 지 결정해야되는
조건문이 필요하다.
따라서, 거리를 계산한다. 큐의 중간을 기준으로 더 앞쪽에 있으면 앞쪽것을 빼서 뒤에 붙이도록 한다.
만약 큐의 중간보다 뒤에 있다면 더 뒤쪽 것을 빼서 앞에 붙이면 된다.
5430번 - AC
해당 테스트케이스마다 함수가 R와 D가 포함된 문자열로 주어진다.
R은 해당 배열을 반대로 하고, D는 첫 번째 수를 지우는 것이다.
주어진 배열을 기능에 따라 구현했을 때 맨 마지막의 출력 결과를 보여주면 된다.
코드 리뷰
import sys
from collections import deque
input = sys.stdin.readline
for _ in range(int(input().strip())):
f, n, A = input().strip(), int(input().strip()), input().strip()[1:-1].split(',')
A = deque(map(int, A)) if n else deque()
r, e = False, False
for op in f:
if op == 'R':
r = not r
elif not A:
e = True
break
else:
A.pop() if r else A.popleft()
print('error' if e else '[' + ','.join(map(str, reversed(A))) + ']' if r else '[' + ','.join(map(str, A)) + ']')사실 이거는 길게 짰을 때 계속 valueError가 나서 gpt와 10번 넘게 시도했는데도
valueError가 계속 나서 짧은 버전으로 시도한 결과이다.
f에는 명령어가 담긴 것, n은 배열의 크기, A는 입력의 배열을 담는다.
입력으로 리스트가 들어오는데 이는 리스트가 아니라 리스트의 형태인 문자열이다.
따라서 진짜 리스트로 구현하기 위해서, 양쪽 문자열의 공백을 제거하고 [1:-1]로 대괄호 부분들을 없앤다.
그리고 split(',')을 하여 숫자만 담긴 리스트로 반환할 수 있다.
나는 역방향 슬라이싱이 처음이라 이게 되게 이해하기 어려웠다.
A = [1,2,3,4,5]
print(A[1:-1]
>>> [2,3,4]이렇게 1번부터 마지막을 제거하고 그 중간단계만 남기게 슬라이싱 하는 기법을 알았다.
우와우!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 신기하군
그리고 print문 안에서 조건문 달아서 해당 조건에 따라 출력하게 하도록 하는 것도 신기하당
자주 애용해야징
후기
챗 gpt는 최고야..
