https://www.acmicpc.net/problem/11866
11866번: 요세푸스 문제 0
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
www.acmicpc.net
문제 해결을 위한 과정
이 문제는 구현 유형의 문제로서 어려운 문제는 아니었지만 문제를 해결하는 데 있어서 생각하는 방식이 중요한 문제였습니다. 문제에서 주어진 예시를 해결해보겠습니다.
다음의 그림은 예시를 푸는 과정입니다. 이 예시에는 N은 7, K는 3입니다.
문제 해결을 위한 팁
이 문제는 위의 그림을 자세히 살펴보면 알 수 있듯이 k번째 원소가 아닌 것들은 다시 뒤에 붙여서 해결한다는 점입니다. 따라서 관찰을 통해 큐를 구현하면 해결할 수 있음을 알 수 있습니다. 파이썬에서 큐 보다 효율적인 deque를 이용해 popleft(), append()를 이용해 해결할 수 있습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
from collections import deque
n, k = map(int, input().split())
q = deque()
for i in range(1, n+1):
q.append(i)
print("<", end="")
i = 0
while True:
i += 1
if i != k:
v = q.popleft()
q.append(v)
else:
v = q.popleft()
if (q):
print(v, end=", ")
i = 0
else:
print(v, end=">")
break
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 1080번: 행렬(Python) (0) | 2022.01.06 |
|---|---|
| 백준 알고리즘 1946번: 신입 사원(Python) (0) | 2022.01.06 |
| 백준 알고리즘 1789번: 수들의 합 (Python) (0) | 2022.01.03 |
| 백준 알고리즘 10610번: 30(Python) (0) | 2022.01.03 |
| 백준 알고리즘 1026: 보물(Python) (0) | 2022.01.03 |