[백준] 11866번: 요세푸스 문제 0 - JAVA

dev-jjun·2023년 1월 26일

boj 알고리즘

코딩테스트 준비

목록 보기

9/11

🔗 문제

BOJ 11866 : 요세푸스 문제 0

난이도 - 실버 5

알고리즘 분류 - 구현, 자료구조, 큐

💬 풀이

다양한 자료구조로 문제 풀이를 시도해보았다.

첫 번째 시도

ArrayList의 remove(x) 메서드에서 파라미터에 해당하는 부분이 인덱스로도 해석될 수 있고, 요소의 값 자체를 나타낼 수도 있어 이를 내부적으로 구분하지 못하는 부분에서 시간을 많이 쏟았다.
-> 이는 ArrayList가 Interger Wrapper 클래스를 사용하므로, 값을 지정해줄 때는 Integer 형으로 타입 캐스팅하는 메소드를 Integer.parseInt(idx)와 같이 명시해줌으로써 구분할 수 있었다.
(결국 혼자 삽질하다가 못 푼 거..ㅎ)

두 번째 시도

iterator를 이용하여 hasnext()가 아니면 다시 첫 인덱스로 돌아가도록 하였다. 첫 번째나 두 번째나 마지막 배열의 인덱스에서 다시 맨 처음으로 돌리는 방식으로 접근했으나 이는 배열의 크기가 점점 줄어들고 삭제되는 위치를 항상 알 수 있는 것이 아니므로 인덱스 값이 유동적이라는 사실을 간과한 풀이였다.

세 번째 시도

문제 알고리즘 분류를 보면 '큐'라고 나와있어 큐를 이용한 풀이를 떠올려보았다. 선입선출이라는 특징에 맞게 루프를 돌면서 중첩 루프로 K번을 내부적으로 돌도록 하였다. K-1번까지는 poll()하고 이를 저장해뒀다가 바로 다시 add(), K번은 poll()하여 StringBuilder로 결과값에 쌓아주었다.

💻 코드

package Baekjoon;

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

public class _11866 {

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Queue<Integer> nums = new LinkedList<>();
        for (int i=1; i<=N; i++)  nums.add(i);



        sb.append("<");
        while (nums.size() > 1) {

            printArr((LinkedList<Integer>) nums);

            int tmp = 0;
            int curr;
            while (tmp < K-1) {
                curr = nums.peek();
                nums.poll();
                nums.add(curr);
                tmp++;
                System.out.println("curr: " + curr + ", tmp: "+ tmp);

            }

            curr = nums.poll();

            sb.append(curr).append(", ");

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


    }


    private static void printArr(LinkedList<Integer> arr) {
        System.out.println("============");
        for (int num : arr) {
            System.out.println(num);
        }
        System.out.println("============");
    }
}