큐(Queue)란
:한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조입니다.
이런 자료 구조를 First In First Out 이라고 해서 FIFO 라고 부릅니다. 선입선출
파이썬 큐(Queue), deque 사용법!
1. deque 만들기
deque : double-ended queue의 약자로 양방향에서 데이터 추가/제거 할 수 있는 자료구조입니다.
- 임포트(import) 하기
from collections import deque2. a_ilst = deque() : deque 형태의 리스트를 만듭니다. 괄호안은(str 타입,list 형태)
a_list = deque('asd')
=> ['a','s','d']3. a_list.append(k) : 뒤에 k를 추가
a_list.appendleft(h) : 앞에 h를 추가
2. a_list.append(k) : 뒤에 k를 추가
=> ['a','s','d','k']
a_list.appendleft(h) : 앞에 h를 추가
=> ['h','a','s','d']
4. .pop() : 맨 오른쪽 값을 돌려주고 리스트에서 삭제
.popleft() : 맨 왼쪽 값을 돌려주고 리스트에서 삭제
a_list.pop()
['a','s']
a_list.popleft()
['s','d']5. a_list.extend() : ()안의 요소를 오른쪽에 붙여서 합칩니다. 괄호안은(str 타입,list 형태)
a_list.extendleft() : ()안의 요소를 왼쪽에 붙여서 합칩니다.
a_list = deque('asd')
=> ['a','s','d']
a_list.extend('7') <--그냥 숫자 7 넣으면 typeError
=> ['a','s','d','7']
b_list = [99]
a_list.extendleft(b_list) <-- 리스트를 합치면 int 값이 들어갑니다.
=> [99,'a','s','d']
print(a_list[0] + 1)
=> 1006. 일반 리스트 문법인 .insert( , ) , .remove( ) 사용가능
a_list.insert( , ) : 쉼표 앞엔 값이 들어갈 index, 뒤엔 넣을 값
a_list.remove('a') : 괄호 안의 값을 찾아 지움, 같은 값이면 왼쪽꺼 1개 지움
a_list.insert(2,'k') : 2번 index에 'k' 삽입
=> ['a','s,'k','d']
a_list.remove('s')
=> ['a','d']7. a_list.reverse() : 내용 좌우 반전
a_list.reverse()
=> ['d','s','a']8. a_list.clear() : 다 지우기
a_list.clear()
=> []9. a_list.rotate(n) : n만큼 요소를 회전시킵니다.
a_list.rotate(n) : 오른쪽으로 n칸 밀어서 맨 오른쪽값을 왼쪽에 붙이기
a_list.rotate(-n) : 왼쪽으로 n칸 밀어서 맨 왼쪽값을 오른쪽에 붙이기
a_list = deque('asd')
=> ['a','s','d']
a_list.rotate(1)
=> ['d','a','s']
a_list.rotate(-1)
=> ['s','d','a']큐를 활용한 문제
요세푸스 문제 0
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 512 MB 56034 31797 26774 56.544%
문제
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
예제 입력 1
7 3
예제 출력 1
<3, 6, 2, 7, 5, 1, 4>
import sys
from collections import deque
input = sys.stdin.readline
n, k = map(int, input().split())
queue = deque([])
asw = []
temp = ""
for i in range(1, n+1):
queue.append(i) # n만큼의 개수를 리스트에 넣어줌
while len(queue) > 0: # 리스트의 길이가 0보다 크면 반복문 실행
for i in range(k-1): # k번째에 죽이고 리스트에 넣어줘야해서 k-1로 죽일 사람 앞에서 멈춤
temp = queue[0] # 제일 앞 값을 변수에 넣고
queue.popleft() # 제일 앞 값을 리스트에서 제거
queue.append(temp) # 다시 넣어줘 맨 뒤로 보냄(교체하는 방식)
asw.append(queue[0]) # k번째 사람 번호를 리스트에 넣고
queue.popleft() # 리스트에서 지움
print("<" + ", ".join(str(x) for x in asw) + ">")