[백준] 1158번 : 요세푸스 문제 - 자바(JAVA)

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

1158번: 요세푸스 문제

 

문제 해석

문제는 사람의 수 N과 제거할 순번인 K를 입력받습니다.

 

초기 시작 자료구조는 다음과 같습니다

1, 2, 3, 4, ......, N

 

여기서부터 순서대로 K번째를 제거합니다.

 

N=5라 가정하여 초기 시작 자료구조는 1, 2, 3, 4, 5 이며 K=2라고 가정해보겠습니다.

 

초기 시작 1, 2, 3, 4, 5

2번째수인 2제거

 

step 1 : 1, 3, 4, 5

굵은글씨 3부터 2번째수인 4제거

 

step 2 : 1,3,5

굵은글씨 5부터 2번째수인 1제거

 

step 3 : 3,4

굵은글씨 3부터 2번째수인 4제거

 

step 4 : 3

굵은글씨 3부터 2번째수인 3제거

 

출력은 <2, 4, 1, 5, 3> 으로 이는 요세푸스 문제입니다.

 

 

문제 풀이 전 설계

중간에 있는 값들을 제거해야하기 때문에 ArrayList보다 LinkedList를 선택하였습니다.

선형자료구조가 아닌 원형자료구조를 구현해야 합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main_1158_요세푸스문제 {

	static int N;
	static int K;

	public static void main(String[] args) throws IOException {

		inputSolutionInfo();
		StringBuilder sb = getJosephusPermutation();
		printJosephusPermutation(sb);
	}

	private static void inputSolutionInfo() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
	}

	private static StringBuilder getJosephusPermutation() {
		List<Integer> peopleList = new LinkedList<Integer>();
		StringBuilder sb = new StringBuilder();

		sb.append("<");
		for (int i = 0; i < N; i++) {
			peopleList.add(i + 1);
		}

		int cnt = 0;
		int index = -1;
		
		while (!peopleList.isEmpty()) {
			
			//세 구문이 cnt % k ==0일때 까지 반복
			int listSize = peopleList.size();
			index = (index + 1) % listSize;			
			cnt++;

			if (cnt % K != 0) {
				continue;
			}
			
			//k=3이라면 cnt=3 index=3						
			if (peopleList.size() == 1) {
				sb.append(peopleList.remove(index) + ">\n");
				continue;
			}
			sb.append(peopleList.remove(index) + ", ");
			index--;			
		}
		return sb;
	}

	private static void printJosephusPermutation(StringBuilder sb) {
		System.out.println(sb.toString());
	}
}

코드에서 peopleList.remove(index) 후에 index를 하나 빼주는 연산이 존재합니다.

 

index--;

 

index를 빼주는 이유는 자료구조가 하나 제거되면서 index들이 당겨지게 되므로 다시 k번째를 올바르게 탐색하기 위해 index를 빼주게 됩니다.

 

이때 index가 0일때 index--를 통해  -1 값이 들어갈 수 있지만 위의 반복문에 +1을 하며 시작하기 때문에 문제가 발생하지 않습니다.