[Java] 백준 풀기 1158 - 요세푸스 문제

자바 백준 1158번

실버 5

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

1158번: 요세푸스 문제

 

 

 

 

 

문제 보기

분류: 자료 구조, 큐

 

 

 

 

 

 

문제 풀기

입력 받을 Queue 인 numQue 와 요세푸스 수를 저장할 numJosephus 를 준비한다.

offer() 을 통해 1 부터 순차적으로 수를 Queue 에 입력 받는다.

모든 수가 저장된 numQue 에서 제일 처음에 들어온 수를 poll() 로 빼내어 맨 뒤에 다시 offer() 로 넣는 과정을 주어진 k - 1 횟수만큼 반복을 한다. 이 과정의 for loop 이 완료될 때마다 그 다음 수를 빼내어  numJosephus 에 넣는다.

주어진 규칙대로 모두 저장된 numJosephus 에서 poll() 로 하나씩 빼내어 제출 형싱에 맞춰 출력한다.

 

 

 

 

 

코드 보기

// 요세푸스 문제
// package boj_1158;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		Queue<Integer> numQue = new LinkedList<Integer>();
		Queue<Integer> numJosephus = new LinkedList<Integer>();
		
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		//
		for (int i = 1; i <= n; i++) {
			numQue.offer(i);
		}
//		System.out.println(numQue.toString());			// TEST PRINT
		
		//
		while (!numQue.isEmpty()) {
			for (int i = 0; i < k - 1; i++) {
				int temp = numQue.poll();
				numQue.offer(temp);
			}
			int jNum = numQue.poll();
			numJosephus.offer(jNum);
		}
//		System.out.println(numJosephus.toString());			// TEST PRINT
		
		// result
		System.out.print("<");
		for (int i = 0; i < n - 1 ; i++) {
			System.out.print(numJosephus.poll() + ", ");
		}
		System.out.print(numJosephus.poll() + ">");

		sc.close();
	}

}