[BOJ] 1158 요세푸스 문제 (Pyhton / 파이썬)

🧷 문제

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

N명의 사람이 원을 이루면서 앉아있을 때, K번째 사람을 모든 사람이 제거될 때까지 계속 반복하는 문제이다.

🛠 풀이

이 문제를 풀 때 어떻게 풀어가야 하는지보다는 어떻게 출력해야 하는지 애를 먹었다.
덕분에 파이썬의 출력형식과 join에 대해서 알아볼 수 있는 기회였다.

Step 1.
 n과 k를 입력받아준 후에 peoples라는 queue를 만들어주었다.
 peoples의 원소가 없어질 때까지 while문을 이용해 k번 째 원소를 popleft해줌과 동시에 res라는 결과 리스트에 append 해주었다.

Step 2.
 res리스트의 원소들을 join함수를 이용하여 문제에서 원하는 포맷으로 출력할 수 있었다.

• Pyhton의 join 함수
  : 리스트에 특정 구분자를 추가하여 문자열로 반환하는 기능을 수행하는 함수이다.
  '구분자'.join(문자열 리스트)의 형태를 가진다. 　ex) '-'.join(['a', 'b', 'c']) => 'a-b-c'

문제를 해결하고 다른 사람의 코드를 봤는데 굳이 queue를 이용하지 않아도 list를 이용해서 해결하니 내 코드와 비교해 훨씬 빠른 시간에 해결한 것을 볼 수 있었다.

🖊 나의 코드

import sys
from collections import deque

input = sys.stdin.readline

if __name__ == "__main__":
    n, k = map(int, input().split())
    res = []

    peoples = deque(range(1, n+1))
    while peoples:
        for _ in range(k-1):
            peoples.append(peoples.popleft())
        res.append(peoples.popleft())


    #     *** list를 이용한 다른 방법 ***
    # peoples_list = list(range(1, n+1))
    # index = 0
    # while peoples_list:
    #     index = (index + k - 1) % len(peoples_list)
    #     res.append(peoples_list.pop(index))

    print(f"<{', '.join(map(str, res))}>")