[자료구조] [BJ1158] 요세푸스 문제

코드 플러스

🚩 문제 설명

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

BJ1158

 

⏱️ 시간 복잡도
▪ 총 N명의 사람을 제거해야한다.
▪ 시간 복잡도는 O(N)이라고 볼 수 있다.

◾ 원을 그리고 있는 사람들을 스텝 순서 대로 없애는 문제

◾ 제거되는 값을 반환한다.

 

 

 

---

 

 

 

✅ 입출력

N: 원을 이루고 있는 사람의 수
K: 제거되는 스텝의 수
return ➡️ 제거되는 사람의 인덱스 수를 순서대로 반환

✔️ 예시

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())  # N: 사람의 수, K: 스텝
que = deque(list(range(1, N + 1)))  # 1부터 N 까지의 큐
ans = []  # 해답 배열

cnt = 0
while que:
    if cnt == K - 1:
        ans.append(str(que.popleft()))
        cnt += 1
        cnt %= K
    else:
        que.rotate(-1)
        cnt += 1
        cnt %= K

print("<"+ ', '.join(ans)[:] + ">")

💬 Point

➡️  deque의 rotate 함수 사용

◾ 한 명씩 뒤로 미뤄가며 카운트를 센다.

◾ 만약 카운트가 K - 1이 되면 ans 배열에 추가한다.

◾ 카운트 되는 수가 K를 넘지않도록 % 연산을 해준다.

◾ join() 함수를 쓸 수 있도록 str() 함수로 배열에 추가해준다.

◾ join() 함수를 사용하여 숫자를 포맷에 맞게 출력한다.

◾ 해당 코드는 Pypy3로 돌려야 채점이 성공된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

# 코드플러스 요세푸스 문제 파이썬

# 백준 1158 파이썬

---