[ALGOSPOT] 알고스팟 JOSEPHUS 조세푸스 문제(Python)

www.algospot.com

[ALGOSPOT] 알고스팟 JOSEPHUS 조세푸스 문제

(Python)

(글쓴날 : 2020.05.29)

 

---

* ALGOSPOT, 알고스팟 JOSEPHUS 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

알고스팟 JOSEPHUS 조세푸스 문제

---

1) 문제

문제 링크 : https://algospot.com/judge/problem/read/JOSEPHUS

algospot.com :: JOSEPHUS

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

원형으로 앉아있는 N명의 병사들이 주어지고, 첫 번째 병사부터 시계방향으로 K 번째마다 자살을 할 때, 최종적으로 남은 두 병사의 번호를 구하는 문제입니다.

 

저의 경우, Python을 사용했습니다.

병사들을 저장한 리스트를 만든 뒤, 자살할 병사의 인덱스를 나타내는 변수 i를 생성해 K-1만큼 더해가며 자살한 병사를 리스트에서 제거하는 식으로 문제를 해결했습니다.

단, i가 리스트의 길이를 초과하면 안되므로, 항상 리스트의 길이만큼 모듈러 연산을 하여 인덱스 초과 에러를 방지하였습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
C = int(input())
 
for _ in range(C):
    N, K = map(int, input().split())
    soldiers = [i + 1 for i in range(N)]
 
    i = 0
    while len(soldiers) != 2:
        del soldiers[i]
        i += K - 1
        i %= len(soldiers)
    
    print(*soldiers)

---