[백준/자료구조] 1158: 요세푸스 문제 - 자바, 파이썬

문제

---

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

1158번: 요세푸스 문제

 

요세푸스 문제란?

---

1차 유대-로마 전쟁 당시 요세푸스(Flavius Josephus)는 동료 40명과 함께 로마군에게 포위됐다. 이들은 투항하는 대신, 제비를 뽑아 둥글게 둘러 앉은 후 두 명씩 건너 뛰고 세 번째마다 자살하기로 하였다. 이렇게 하여 39명이 죽은 뒤 요세푸스는 아직 살아남은 동료와 투항했고, 훗날 역사가가 되어 이 일을 기록에 남겼다고 한다.

[네이버 지식백과] 요세푸스 문제 (365일 수학)

 

이를 애니메이션으로 나타내면 다음과 같다.

이미지 출처: The Josephus Problem - Tom Lord (medium)

 

풀이 - 파이썬

---

person, num = map(int,input().split()) # 입력
entire_list = [] # 전체 사람 리스트
result = [] # 결과를 출력할 리스트
popNum = 0 # 꺼낼 사람의 번호 (여기서는 0부터 n-1)

# 전체 사람 리스트에 0부터 n-1명의 번호를 입력
for i in range(person): 
    entire_list.append(i+1)

# 전체 사람 리스트가 빌 때까지 반복함
while len(entire_list) > 0:  
    popNum = (popNum + (num-1)) % len(entire_list) # 꺼낼 사람의 번호를 선택
    
    # 꺼낸 사람을 결과를 출력할 리스트에 넣고 전체 사람 리스트에서 제외함
    popElement = entire_list.pop(popNum) 
    result.append(str(popElement))

print("<%s>" %(", ".join(result)))

 

풀이 - 자바(파이썬과 로직은 동일)

---

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class BOJ_1158 {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int N = sc.nextInt();
		int K = sc.nextInt();
		
		List<Integer> people = new LinkedList<>();
		List<Integer> result = new LinkedList<>();
		for (int i = 1; i <= N; i++) people.add(i);
		
		int popNum = 0;
		while(people.size() > 0) {
			popNum = (popNum + (K-1)) % people.size();
			int popElement = people.remove(popNum);
			result.add(popElement);
		}
		sb.append("<");
		for (int i = 0; i < result.size()-1; i++) {
			sb.append(result.get(i)).append(", ");
		}
		sb.append(result.get(result.size()-1));
		sb.append(">");
		System.out.println(sb);
	}
}

 

풀이 - 자바 (큐를 이용한 입출력)

---

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

// 메모리: 293936KB, 시간: 584ms, 코드길이 647B 
public class BOJ_1158 {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int N = sc.nextInt();
		int K = sc.nextInt();
		
		Queue<Integer> people = new LinkedList<>();
		for (int i = 1; i <= N; i++) {
			people.add(i);
		}
		sb.append("<");
		while(!(people.isEmpty())) {
			for(int j = 0; j < K-1 ; j++) {
				people.add(people.poll());
			}
			sb.append(people.poll());
			if(people.size() != 0) {
				sb.append(", ");
			}
		}
		sb.append(">");
		System.out.println(sb);
	}
}

 

 

 

참고

https://www.youtube.com/watch?v=uCsD3ZGzMgE&ab_channel=Numberphile