[백준 1158] 요세푸스 문제 - 자바

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

1158번: 요세푸스 문제

---

1. 풀이

이번 문제는 요세푸스 수열을 푸는 문제이다.

 

리스트를 사용해서 풀이를 하고, 백준 강의를 보았는데 큐를 사용하면 더 이해가 쉽게 풀 수 있는 것 같다.

 

순서가 차례대로 돌아가기 때문에, 맨 앞에 있는 것을 m-1만큼 pop과 push를 반복하여, 맨 앞에 있는 숫자를 pop을 하고

 

결과에 붙이면 된다.

 

---

2. 코드

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		Queue<Integer> queue = new LinkedList<Integer>();
		StringBuilder result = new StringBuilder();
		
		// n만큼의 숫자 큐에 넣기.
		for(int i = 1; i <= n; i++) {
			queue.offer(i);
		}
		
		result.append("<");
		// 매 숫자마다.
		for(int i = 0; i < n-1; i++){
			// m번씩 pop, push를 통한 순서 바꾸기.
			for(int j = 0; j < m-1; j++) {
				queue.offer(queue.poll());
			}
			result.append(queue.poll()+", ");
		}
		
		result.append(queue.poll()+">");
		System.out.println(result);
		
		sc.close();
		return;
	}
}