[Baekjoon] 1158. 요세푸스 문제(Josephus Permutation)

 

코테 스터디가 좋은 연이 되어서, 99클럽 알고리즘 스터디 1기에도 참여하게 되었습니다 😀

클럽장님과 Q&A 시간 후에 자극받아서 문제를 조금 풀어보았어요.

 

 

---

💡 문제

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

 

요세푸스 순열을 출력하는 문제였습니다. 생각보다 간단하지만 무서운 문제 

n명의 사람이 원형으로 앉아 있을 때, 매번 k 번째 사람을 제거해 나가면서 최후의 생존자를 찾는 문제입니다. 
이 문제에서는 제거되는 사람들의 순서를 출력하는 것이 목표 ! 

 

요세푸스 순열이란?

n과 k가 자연수이고, k < n이라고 가정한다. n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.
출처 : 위키백과

 

 

요구사항

 

• n : 사람의 수
• k : 제거될 사람의 순서(갱신되는 새로운 원에서 k번째 사람 제거)

   ⚠️ 출력형식 : 리스트 [ ] 대신 꺽쇠 괄호 < > 로 출력해야 합니다 . 이 부분 놓쳐서.. 풀이 실패하고 당황황당머쓱 ㅎㅎ;;

 

 

---

👀 해결 과정

리스트를 원 형태로 사용할 방법에 대해 생각했습니다.

 

1. 1번부터 n번까지의 사람들을 리스트로 준비 (people)

2. k 번째 사람을 찾아 제거하며 그 순서를 기록 (out_index)

3. 리스트 양끝이 붙어 돌 수 있게(끝을 넘지않게), mod 연산을 통해 순환 구조로 인덱스 계산

 

# 1~N 번, K 번째 사람 제거
# 1. 입력 
n, k = map(int, input().split())

# 2. K 번째 사람 제거 후 원만들어서 다시 k번째 사람 제거
def josephus(n,k):
    people = list(range(1, n+1))
    result = []
    out_index = 0

    while people:
        # 제거하고 원 만들기
        out_index = (out_index + k - 1) % len(people)
        result.append(people.pop(out_index))

    print("<"+ ", ".join(map(str, result)) + ">")

# 3. 출력 : 요세푸스 순열
josephus(n,k)

 

 

 

---

🗨️ 배운 점

• 문제를 잘 보고, 특히 출력 형식도 놓치지 말아야 좋은 결과를 얻을 수 있다.
• 리스트 순환 처리를 위해 mod 연산이 유용하다.
• join()을 사용하면 리스트의 각 요소 사이에 원하는 걸 집어넣을 수 있다.