백준 1158 - 요세푸스 문제

Java

1158 번 - 요세푸스 문제

문제

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

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

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

접근 방법

원을 Queue로 생각한다. n개의 수가 차례로 저장된 Queue에서 k번째 수를 제거하는 방법은,

1. Queue의 앞에서 k - 1개의 사람을 Queue에 마지막으로 보낸 후
2. top에 있는 사람을 제거하는 방법으로 구현한다.
   예를 들어 설명하면,
   Queue에 [1,2,3,4,5,6,7]가 있으면, 3번째 사람을 제거해본다.
   k - 1번 사람을 뒤로 보내면 [3,4,5,6,7,1,2]가 되며,
   제일 앞의 값인 3을 poll 한다. [4,5,6,7,1,2]
   다음 k - 1번 이동하면, [6,7,1,2,4,5] 이므로, 6을 제거하여 [7,1,2,4,5]가 된다.

구현

Queue에 초기 1 ~ n 의 값을 차례로 넣어준다.
Queue가 empty가 될 때까지 반복을 하며, k - 1 만큼 반복하여 poll 하여 offer 넣는다.
이후 peek 값은 k번째 사람이므로 poll 하여 제거한다.

결과 값을 보면 <a,b> 형태로 이루어져 있다.
위 과정이 끝난 뒤는 마지막 값이 “, “으로 되어 있으므로, replace로 제거하고 “>”로 수정한다.

코드

/*
 * 요세푸스 문제
 * https://www.acmicpc.net/problem/1158
 */
import java.util.*;
import java.io.*;

public class Main {
	
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	int n = stoi(stk.nextToken());
    	int k = stoi(stk.nextToken());
    	
    	Queue<Integer> yose = new LinkedList<Integer>();
    	
    	for(int i = 1; i <= n; i++) {
    		yose.offer(i);
    	}
    	StringBuilder sb = new StringBuilder();
    	
    	sb.append("<");		// 출력 값 세팅
    	
    	while(!yose.isEmpty()) {		// k의 간격이면, k - 1 횟수 만큼 queue의 앞의 값을 뒤로 보낸다. 
    		for(int i = 0; i < k - 1; i++) {
    			yose.offer(yose.poll());
    		}
    		sb.append(yose.poll()).append(", ");	// k번째 수 제거
    	}
    	
    	sb.replace(sb.length() - 2, sb.length(), ">");	// 마지막 문자열이 ", "이 되므로  ">"으로 바꿔준다.
    	System.out.println(sb.toString());
    	br.close();
    }
    static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐★★★★

후기

이전에도 접했던 문제이기 때문에 쉽게 해결 가능했다.

개선할 점

없