[백준 1158] 요세푸스 문제

 

[문제 바로가기]

1158번: 요세푸스 문제

 

💡풀이💡

앞에서부터 순서를 세어 K번째가 되면 순서에서 빠지고,  K번째가 아닌 사람은 뒤로 가서 다시 줄을 선다는 것과 동일

>>> 큐를 이용해서 풀기

 

1. 입력 값 받기

N과 K를 입력 받아 1~N번까지 수를 queue에 추가한다.

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringBuilder sb = new StringBuilder();
	StringTokenizer st = new StringTokenizer(br.readLine());
	ArrayDeque<Integer> q = new ArrayDeque<>();
	int N = Integer.parseInt(st.nextToken());
	int K = Integer.parseInt(st.nextToken());
		
	for(int i=1; i<=N; i++) {
		q.offer(i);
	}

 

2. K번째 사람 제거

모든 사람들이 제거 될 때까지 반복하기 때문에 queue에 원소가 있다면 계속 반복한다.

cnt라는 변수를 통해 현재 몇 번째인지 카운트를 했는데, 첫 번째 사람부터 1번으로 세어야 하기 때문에 초기화를 0이 아니라 1로 했다.

 

한 사람이 제거되고 나면 다시 cnt를 1로 초기화 한다. 입력 형식을 맞추기 위해 남은 원소의 크기가 1일 때 콤마와 공백을 없애줬다.

	sb.append("<");
	int cnt = 1;
	while(!q.isEmpty()) {
		if(cnt == K) {
			if(q.size() == 1) sb.append(q.poll());
			else sb.append(q.poll()).append(", ");
			cnt = 1;
		}
		else {
			q.offer(q.poll());
			cnt++;
		}
	}
	sb.append(">");

 

 

전체 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		ArrayDeque<Integer> q = new ArrayDeque<>();
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
		for(int i=1; i<=N; i++) {
			q.offer(i);
		}
		
		sb.append("<");
		int cnt = 1;
		while(!q.isEmpty()) {
			if(cnt == K) {
				if(q.size() == 1) sb.append(q.poll());
				else sb.append(q.poll()).append(", ");
				cnt = 1;
			}
			else {
				q.offer(q.poll());
				cnt++;
			}
		}
		sb.append(">");
		System.out.println(sb.toString());
	}
}