일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 26 | 27 | 28 |
Tags
- object detection
- 다익스트라
- 알고리즘
- DP
- 플로이드 와샬
- 가끔은_말로
- 미래는_현재와_과거로
- 문자열
- dropout
- 분할 정복
- c++
- Overfitting
- 가끔은 말로
- 2023
- pytorch
- 너비 우선 탐색
- 조합론
- lazy propagation
- 백트래킹
- dfs
- NEXT
- 크루스칼
- BFS
- 세그먼트 트리
- 우선 순위 큐
- back propagation
- 회고록
- tensorflow
- 이분 탐색
- 자바스크립트
Archives
- Today
- Total
Doby's Lab
백준 1158번: 요세푸스 문제 (Python) 본문
https://www.acmicpc.net/problem/1158
1158번: 요세푸스 문제
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
www.acmicpc.net
Level: Silver IV
Solved By: Queue
파이썬에서는 Queue를 사용하기 위해서 deque
을 사용합니다. queue를 사용하지 않는 이유는 파이썬에서 제공하는 queue는 멀티스레드를 위해 동기화 과정을 거치기 때문에 문제풀이용으로는 좋지 않습니다.
그래서 deque을 사용하여 문제를 풀 수 있으며, 아래와 같이 가져올 수 있습니다.
from collections import deque
그리고, deque에서는 아래와 같이 원소를 push, pop 하며 양 옆으로 가능합니다.
dq = deque()
dq.append(element)
dq.pop()
dq.appendleft(element)
dq.popleft()
문제를 풀이하는 방식은 덱에 1부터 N까지 push를 해두고, 반복되는 count가 K가 될 때마다 결과 값을 담을 list에 담아줍니다. count가 K가 되지 않는 반복에서는 원처럼 덱을 사용하기 위해 pop을 시킨 원소를 뒤에 push 합니다.
import sys
from collections import deque
N, K = map(int, sys.stdin.readline().split())
queue = deque([i for i in range(1, N + 1)])
res = []
cnt = 0
while len(queue) > 0:
temp = queue.popleft()
queue.append(temp)
cnt += 1
if cnt == K:
res.append(temp)
queue.pop()
cnt = 0
print("<", end='')
for i in range(0, len(res)):
print(res[i], end = '')
if i != len(res) - 1:
print(", ", end='')
print(">", end='')
728x90
'PS > BOJ' 카테고리의 다른 글
백준 5430번: AC (Python) (0) | 2023.10.28 |
---|---|
백준 1978번: 소수 찾기 (Python) (0) | 2023.10.24 |
백준 1182번: 부분수열의 합 (Python) (0) | 2023.08.26 |
백준 1920번: 수 찾기 (Python, C++) (0) | 2023.08.17 |
백준 1181번: 단어 정렬 (Python, C++) (0) | 2023.07.30 |