[BJ] 1158. 요세푸스 문제

1158. 요세푸스 문제

www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

// 210209 

import java.io.*;
import java.util.*;

public class Main_1158_요세푸스문제 {

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_1158_요세푸스문제.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");
		StringBuilder sb = new StringBuilder();
		sb.append("<");
		
		int N = Integer.parseInt(str.nextToken());
		int K = Integer.parseInt(str.nextToken());
		
		Queue<Integer> queue = new LinkedList<Integer>();

		for(int i=1; i<=N; i++) {
			queue.offer(i);
		}
		
//		int idx = 1;
		
//		while (! queue.isEmpty()) {
//			if (idx % K == 0) {
//				sb.append(queue.poll() + ", ");
//			} else {
//				queue.offer(queue.poll());
//			}
//			idx++;
//		}
		
		while (! queue.isEmpty()) {
			
			for(int i=0; i<K-1; i++) {
				queue.offer(queue.poll());
			}
			
			sb.append(queue.poll() + ", ");
		}
		
		sb.setLength(sb.length()-2);
		sb.append(">");
		System.out.println(sb.toString());
		br.close();
	} // main

}

 

중간 원소를 삭제하는 작업이 반복되기 때문에 처음에는 링크드 리스트를 생각했다. 

그러나 숫자가 원을 이루는 상황을, 맨 앞의 숫자가 맨 뒤로 가서 붙는다는 상황으로 생각한다면 큐로 푸는 것이 훨씬 편했다.