[백준] 1158 요세푸스 문제 - Data Structure / Java

• 문제 링크

1158번: 요세푸스 문제

 

• 풀이 과정

문제에 제시된 7(n), 3(k) 입력 값으로 순열의 변화를 나타내면 아래와 같다.

1 2 3 4 5 6 7 -> 4 5 6 7 1 2 -> 7 1 2 4 5 -> 4 5 7 1 -> 1 4 5 -> 1 4 -> 4 

이렇게 붉은 색으로 마킹한 k번째 수들이 모여 3 6 2 7 5 1 4 요세푸스 순열이 구해진다.

 

우선 1 ~ n 까지 오름차순으로 Queue 에 저장 후,

k-1 번의 횟수만큼 큐의 맨 앞의 값을 poll()하여 큐의 맨 뒤로 삽입한다.

이런식으로 k번째 수가 큐의 맨 앞에 위치하게 되며

해당 값을 요세푸스 순열의 값으로써 StringBuilder 에 쉼표와 함께 더한다.

 

while 문이 큐의 크기가 1일 때까지 반복되며, 남은 한 개의 원소를 마지막으로 StringBuilder 에 더하여

문제에서 요구한 문자열 형태로 구현하여 출력한다.

 

• 풀이 코드

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));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		Queue<Integer> q = new LinkedList<>();
		for (int i = 1; i <= n; i++) {
			q.offer(i);
		}

		sb.append("<");
		while (q.size() != 1) {
			for (int i = 0; i < k - 1; i++) {
				q.offer(q.poll());
			}
			sb.append(q.poll() + ", ");
		}
		sb.append(q.poll() + ">");
		
		bw.write(sb + "\n");
		bw.flush();
	}

}