[백준 - Java] 1158번 : 요세푸스 문제

문제

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

 

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

 

설명

처음엔 이게 무슨말인지가 제일 이해가 안 갔다.

아래 표를 보고 이해해보자!

Input : 7 3
1 2 3 4 5 6 7	3번째	1 2 3
4 5 6 7 1 2		4 5 6
7 1 2 4 5		7 1 2
4 5 7 1		4 5 7
1 4 5		1 4 5
1 4		1 4 1
4		4 4 4
Output : 3 6 2 7 5 1 4

 

Input : 5 4
1 2 3 4 5	4번째	1 2 3 4
5 1 2 3		5 1 2 3
5 1 2		5 1 2 5
1 2		1 2 1 2
1		1 1 1 1
Output : 4 3 5 2 1

 

위의 표와 같이 요세푸스 순열이 만들어진다!

 

구현

LinkedList를 이용하고 마치 커서와 같은 변수를 두어 푸는 방법도 시도해봤지만, 큐를 이용하면 확실히 더 간단하게 처리할 수 있었다.
큐에 N까지의 숫자를 저장한 뒤, 큐가 빌 때까지 K번째의 값을 제거하는 것이다.
아래 그림을 참고해보자.

위와 같이 K번째로(그림에서 K = 4) 걸린 숫자가 아닌 경우는 poll과 add를 통해 큐의 맨 뒤로 이동시켜준다.
그리고 K번째 순서가 되면 그때의 숫자를 poll을 통해 제거해주는 것이다.
이를 큐가 빌 때까지 반복하며 요세푸스 순열을 만드는 것이다.

K = 4번째가 되었을 때의 큐의 모습은 위에 그려진 그림과 같다.

 

K의 값보다 큐의 사이즈 값이 작아졌지만 오른쪽의 큐의 모습처럼 큐가 빌때까지 for문을 통해 반복될 것이다.

 

while(!qu.isEmpty()) { // N명의 사람이 모두 제거될 때까지, 즉 큐가 빌 때까지 반복 
	for(int j = 0; j < K; j++) { // K번째를 제거하기 위한 루프 
    	if(j == K-1) { // K번째 순서 도착 
        	sb.append(qu.poll() + ", ");  // K번을 제거 
   		} else { 
    		qu.add(qu.poll()); // K번이 아닐 때에는 맨 뒤로 이동 
    	} 
    } 
}

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		sb.append("<");
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		Queue<Integer> qu = new LinkedList<Integer>();
		for(int i = 0; i < N; i++) { // 큐에 N까지의 수 차례로 넣어주기
			qu.add(i+1);
		}

		while(!qu.isEmpty()) { // N명의 사람이 모두 제거될 때까지, 즉 큐가 빌 때까지 반복 
			for(int j = 0; j < K; j++) { // K번째를 제거하기 위한 루프
				if(j == K-1) {
					sb.append(qu.poll() + ", "); // K번을 제거
				} else {
					qu.add(qu.poll()); // K번이 아닐 때에는 맨 뒤로 이동
				}				
			}
		}
        
		bw.write((sb.substring(0, sb.length()-2) + ">").toString());
		bw.flush();
		bw.close();
	}
}

*좀 더 효율적인 방법이 있지 않을까?

나머지(%) 연산 이용해 보기

GITHUB

https://github.com/KwonMinha/BOJ/blob/master/BOJ%231158/src/Main.java

KwonMinha/BOJ