백준 > 요세푸스 문제

요세푸스 문제

M명의 인원이 원형으로 앉아있고 K번째를 사형할 때, 사형되는 순서를 출력하는 문제.

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] params = br.readLine().split(" ");
        int N = Integer.parseInt(params[0]);

        ArrayList<Integer> arrList = new ArrayList<>();

        for (int i = 1; i <= N; i++) {
            arrList.add(i);
        }

        int interval = Integer.parseInt(params[1]);
        int next = interval - 1;

        bw.append("<");

        while (arrList.size() > 0) {
            int target = arrList.size() > next ? arrList.get(next) : arrList.get(0);
            if (arrList.size() == 1) {
                bw.append(target + "");
            } else  {
                bw.append(target+ ",");
            }

            if (arrList.size() > next) {
                arrList.remove(next);
            } else {
                arrList.remove(0);
            }

            for (int i = 0; i < next; i++) {
                if(arrList.size() > 0) {
                    arrList.add(arrList.remove(0));
                }
            }
        }

        bw.append(">");
        bw.flush();
        bw.close();
    }
}

결과

예제는 제대로 출력하지만 틀렸음.

오답노트

• arrayList가 아니라 Queue로 구현하면 arrList.remove(0)식으로 인덱스를 하드코딩하지 않아도 된다.
• size가 1일때까지 반복을 수행하고, 나머지는 ,을 붙이지 않으면 if 조건 분기처리가 불필요하다.

package src.baekjoon;

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] params = br.readLine().split(" ");
        int N = Integer.parseInt(params[0]);

        Queue<Integer> queue = new LinkedList<>();
        int interval = Integer.parseInt(params[1]);

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

        bw.append("<");

        while (queue.size() > 1) {
            for(int j = 0; j < interval -1; j++) {
                queue.add(queue.poll());
            }
            bw.append(queue.poll() +", ");
        }

        //마지막 , 없는 숫자
        bw.append(queue.poll()+">");
        bw.flush();
        bw.close();
    }
}

3번째마다 사형시킨다면, 1번째와 2번째를 큐 맨 뒤에 추가하고
사형할 3번째를 꺼내서 버퍼라이터에 추가하는 로직이다.

어떻게 할 지는 코드숨 강의에서 힌트를 얻어 알아냈지만,
자료구조를 더 알맞게 사용하지 못한 것이 아쉽다.

소요 시간

1.5일