[백준]1158번 요세푸스 문제(JAVA)

0. 문제 링크

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

1158번: 요세푸스 문제

 

1. 문제 설명

1) 1번부터 N번까지 N명의 사람이 원을 이루며 앉아 있음

2) 순서대로 K번째 사람 제거를 반복한 후 제거된 사람의 순서인 (N, K)-요세푸스 순열 구하기

 

2. 입출력

// input
7 3

// output
<3, 6, 2, 7, 5, 1, 4>

 

3. 코드

import java.util.*;

public class b1158 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(); // N명의 사람
		int K = sc.nextInt(); // K번째 사람 제거
		StringBuilder sb = new StringBuilder();
		
		ArrayList<Integer> l = new ArrayList<Integer>(); // ArrayList로 구현
		int[] arr = new int[N]; // 정답 배열
		for(int i = 1; i <= N; i++) {
			l.add(i);
		}
		int index = 0;
		for(int i = 0; i < N; i++) {
			index = index + K - 1; // index 구하기
			if(index >= l.size()) { // index가 l.size()보다 크거나 같으면 크기만큼 빼기
				index -= l.size() * (index / l.size());
			}			
			
			arr[i] = l.get(index); // 정답 배열에 추가
			l.remove(index); // 요소 삭제
		}
		
		// 출력
		System.out.print("<");
		for(int i = 0; i < arr.length; i++) {
			if(i == 0) 
				System.out.print(arr[i]);
			else
				System.out.print(", " + arr[i]);
		}
		System.out.print(">");
	}

}

 

실행 결과

 

4. 회고

1) 처음에 생각했을 때에는 맨 앞과 맨 뒤가 연결된 원형 LinkedList를 생각했는데 어떻게 구현해야 할지 감이 잡히지 않아서 우선 ArrayList로 구현해봄

2) K번째에 해당하는 요소를 제거함으로써 ArrayList의 수정, 삭제가 용이하다는 장점을 살림

3) l.size()를 이용하여 index 값을 유효한 범위로 조정

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Baekjoon/b1158.java