[BOJ 백준] -요세푸스 문제0 11866 Java

9921 단어 algorithmbojalgorithm


📌 문제설명

n명의 사람이 순서대로 쭉 앉아있다. ( 각 사람은 번호표를 들고있다.)
k번째 사람을 뽑아서 그 사람이 들고있는 번호표를 출력한다.
모든 사람을 뽑을 때까지 반복한다.

Queue를 이용해서 풀었다.

  • k-1번째까지 큐에서 뽑아서 뒤로 넣는다.
    poll() -> offer()
  • k번째 사람을 뽑는다.
  • 위 두 절차를 Queue의 사이즈가 1이 될 때까지 반복한다.
  • Queue의 사이즈가 1이되면 반복을 종료하고 Queue에 남은 사람을 출력하고 종료한다.

K번째 사람이 발견될 때마다 출력해주면 되는건데 출력형식이 쪼금 이상해서 출력형식까지 신경써줘야 한다.

package com.example.boj;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import java.util.*;

public class Q11866 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        Queue<Integer> queue = new LinkedList<>();

        for (int i=1;i<=n;i++) {
            queue.add(i);
        }

        StringBuilder sb = new StringBuilder("<");
        while (queue.size() > 1) {
            // k-1번 앞에서 뽑아서 뒤로 넣는 작업 반복 (poll -> offer)
            for(int i=0;i<k-1;i++) {
                int tmp = queue.poll();
                queue.offer(tmp);
            }
            // k번째 사람 출력 (StringBuilder에 추가)
            sb.append(queue.poll() + ", ");
        }

	// 큐에 남은 마지막사람을 출력
        sb.append(queue.poll());
        sb.append(">");

        System.out.println(sb.toString());
    }
}

좋은 웹페이지 즐겨찾기