[백준알고리즘] 1158, 1168번: 요세푸스 문제, 요세푸스 문제 2 -Python

[백준알고리즘] 1158, 1168번: 요세푸스 문제, 요세푸스 문제 2 -Python

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

1158번: 요세푸스 문제

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

1168번: 요세푸스 문제 2

* 1168번은 재채점으로 현재 통과되지 않습니다. 시간내서 다시 풀어보겠습니다. (20210203)

* 먼저, 요즘 C++로 풀고 있기 때문에 C++로 풀어보았고 꽤 오랜시간이 걸렸습니다.. 자세한 내용은 아래 링크에 포스팅해두었습니다. (20210205)

[백준알고리즘] 1168번: 요세푸스 문제 2 -C++ (tistory.com)

---

두 문제가 같은 문제이다. 다른 점은 메모리 제한과 처리 시간제한이 다르다. 하나의 코드로 두 문제 모두 통과했다.

원형으로 앉아있을 때 순서대로 K번째 인원을 한 명씩 모두 제거할 때 제거되는 순서를 구하면 된다.

 

파이썬을 가지고도 원형 링크드 리스트(Circular Linked List)를 만든 분도 계셨고, 바로바로 출력하시는 분들도 계셨다. 대부분은 while로 현재 남아있는 인원의 리스트를 돌리면서, 한 번 반복시 한 명을 검사하는 것이 아닌 한 번 반복 시 한 명을 제거하도록 코드를 짜셨다. index를 설정해 K-1번을 지나 K번째 사람을 선택하도록 남은 인원 수의 나머지 연산을 통해 인덱싱 하도록 했다.

 

나 같은 경우에는 deque을 이용했다. collections 모듈의 deque 클래스를 이용해 rotate를 할 수 있었다. deque은 원형 링크드 리스트처럼 회전도 가능하며 어느 쪽으로든 삽입, 삭제가 가능하다.

 

rotate() 메서드의 경우에는 인자가 음수일 경우에 왼쪽으로 회전하며 양수가 주어지면 오른쪽으로 회전한다.

table = deque([a, b, c])가 있을 때 table.rotate(1)의 결과는 [c, a, b]이며, table.rotate(-1)의 결과는 [b, c, a]이다.

 

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())
dq = deque([i for i in range(1, N+1)])
res = []
while dq:
    dq.rotate(-K+1)
    res.append(str(dq.popleft()))

sys.stdout.write("<"+", ".join(res)+">")

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다