[Java] 백준 #1158 요세푸스 문제

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

1158번: 요세푸스 문제

• 1번부터 N번까지 N명의 사람이 원을 이루며 앉아있음
• 양의정수 K → 순서대로 K번째 사람 제거 → N명이 제거될 때까지
• (N, K) 요세푸스 순열 구하기

💡 알고리즘

자료구조, 큐

💡 접근

처음에 중간에 원소가 나가면 인덱스도 하나씩 줄어들어야 하겠구나 라는 잘못된 생각을 해서 큐를 생각해내지 못했다.

(규칙만 추가하며 산으로 가던 코드)

 int idx = K - 1;
 LinkedList<Integer> res = new LinkedList<Integer>();
 while(list.size() > 0){
		 res.add(list.get(idx));
     list.remove(idx);
     if ((idx + K) > list.size()){
		     idx = K - (list.size() - idx) - 1;
     } else {
         idx += K - 1;
     }

Queue를 활용하여 K번째인지만 확인해서 K번째 → 꺼내고, 아니면 → 뒤로 넘기면 된다.

💡 코드

import java.io.*;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class BOJ_1158 {
    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());

        StringBuilder sb = new StringBuilder();
        sb.append("<");

        LinkedList<Integer> queue = new LinkedList<Integer>();
        for(int i = 1; i <= N; i++){
            queue.add(i);
        }

        while(queue.size() > 1){
            // K번째면 빼서 sb에 추가, 아니면 queue 뒤로 추가
            for (int i = 0; i < K; i++){
                if (i == K-1){
                    sb.append(queue.poll() + ", ");
                } else{
                    queue.add(queue.poll());
                }
            }
        }

        sb.append(queue.poll() + ">");
        System.out.println(sb);
    }
}

💡 정리

딱봐도 자료구조 문제일 땐, 하나씩 움직여가며 생각해보기

인덱스가 아니라 몇 번째인지가 중요하다.