-
백준 1158, 백준 11866 - 요세푸스 문제BOJ-Algorithm 2022. 1. 14. 10:43
https://www.acmicpc.net/problem/1158
1158번: 요세푸스 문제
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
www.acmicpc.net
https://www.acmicpc.net/problem/11866
11866번: 요세푸스 문제 0
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
www.acmicpc.net
문제 설명이 아예 똑같은 문제다. 다만 1158번이 조금 더 초기 K,N에 대한 입력값의 최대치 상한이 높다.
이 문제는 큐(Queue)로 푸는 문제다. 보통 큐를 구현하라고 하면 Python에서는 list로 구현하는 게 일반적인데, list는 구조적으로 다른 언어(Java, C 등)의 array와 같은 개념이다. 문제는 이런 array는 무작위 접근에 최적화된 자료구조이기 때문에 pop(0)이나 insert(0, x)는 성능적으로 매우 불리하다. 이렇게 되면 시간복잡도가 O(N)이 되어서 데이터가 많이 들어있을수록 해당 명령을 수행하는 데 시간이 오래 걸리기 때문이다. 이를테면, pop(0)으로 첫 값을 제거하게 되면 그 뒤에 있는 모든 데이터를 다 한 칸씩 차례차례로 당겨줘야 하고, insert로 맨 앞에 데이터를 삽입하게 되면 그 전에 모든 데이터를 뒤로 한 칸씩 다 밀어줘야 하기 때문에 시간이 너무 오래 걸린다.
Python에서는 보다 효과적인 Queue 구현을 위해, collections라는 모듈에서 deque(Double-Ended-QUEue, DEQUE)라는 자료구조를 지원해준다. Double-Ended라는 말에서 볼 수 있듯 이 자료구조는 데이터를 앞에서도 넣을 수 있고(Queue), 데이터를 뒤에서도 넣을 수 있다(Stack).
deque는 list의 메소드에 존재하지 않는 popleft()를 제공해 준다. 이는 첫 번째 데이터를 제거할 수 있게 된다. 시간 복잡도는 O(1)이다.
deque의 appendleft(x)를 사용하면, 데이터를 맨 앞에 삽입할 수 있게 된다. 시간 복잡도는 O(1)이다.
대신 deque도 i번째 데이터에 접근하기 위해서는 맨 앞/뒤부터 순차적으로 접근해야 하므로 이는 O(N)의 시간복잡도를 갖는다.
참고 : https://www.daleseo.com/python-queue/
파이썬에서 큐(queue) 자료 구조 사용하기
Engineering Blog by Dale Seo
www.daleseo.com
from collections import deque n,k = map(int, input().split()) arr = deque([i for i in range(1,n+1)]) out_arr = [] while len(arr)>0: for i in range(k): if i<k-1: arr.append(arr.popleft()) else: out_arr.append(arr.popleft()) print("<", end='') for num in out_arr: if num!=out_arr[-1]: print(f'{num},',end=' ') else: print(f'{num}',end='') print(">")
문제로 돌아와서, n,k 값을 입력받고, 배열을 deque로 생성한 뒤 deque 내에는 1부터 n까지의 숫자를 집어넣는다. 그리고 제거되는 순서대로 값을 집어넣을 out_arr을 만든다.
deque 내에 모든 요소가 없어질 때까지, 매 번 요세푸스에서 K번째 사람이 되기 전까지는 맨 앞의 요소를 맨 뒤로 보내줘야 한다. 그러므로 arr.popleft()한 값을 그대로 다시 arr.append()로 뒤로 보내준다. 만일 K번째 사람이라면, popleft한 것을 out_arr로 보내준다.
이후 문제에서 요구하는 출력 양식에 맞게 출력해준다.(개인적으로 이 쪽이 조금 더 구현하기 귀찮았다.)
'BOJ-Algorithm' 카테고리의 다른 글
백준 10819 - 차이를 최대로 (0) 2022.01.15 백준 1003 - 피보나치 함수 (0) 2022.01.14 백준 1037 - 약수 (0) 2022.01.13 백준 11659 - 구간 합 구하기 4 (0) 2022.01.12 백준 2435 - 기상청 인턴 신현수 (0) 2022.01.12