[백준] JAVA - 1158.요세푸스 문제

N명이 모두 제거될때까지 계속 순열을 돌아가면서 K번째 사람을 제거하는 문제입니다. 

 

1. K번째를 원순열에서 지워줘야하기 때문에 현재까지 지나온 횟수인 (cnt % K) 연산을 사용해서 K번째 인지를 체크합니다.

2. K번째 사람이라면 큐에서 pop을 해주고 결과값에 추가해줍니다.

3. K번째 사람이 아니라면 큐의 맨 앞 원소를 큐의 맨 뒤에다가 넣어줍니다.

4. 큐가 다 빌때까지 이 과정을 반복합니다.

 

마지막으로 결과를 출력할때 정해진 출력 형식이 있기 때문에 마지막 문자열에서 sb.deleteCharAt(sb.lastIndexOf(",")) 를 사용하여 ',' 와 공백을 제거해줬습니다.

Java 코드

package com.ssafy.off;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Baekjoon_1158_요세푸스문제 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		sb.append("<");
		
		String[] s = br.readLine().split(" ");
		int N = Integer.parseInt(s[0]);
		int K = Integer.parseInt(s[1]);
		
		Queue<Integer> q = new LinkedList<>();
		for (int i = 1; i <= N; i++) {
			q.add(i);
		}
		int cnt = 1;
		while(!q.isEmpty()) {
			if (cnt % K == 0) {
				sb.append(q.poll()).append(", ");
			}else {
				q.add(q.poll());
			}
			cnt += 1;
		}
		
		sb.deleteCharAt(sb.lastIndexOf(","));
		sb.deleteCharAt(sb.lastIndexOf(" "));
		sb.append(">\n");
		System.out.print(sb);
	}

}