11866 - 요세푸스 문제 0

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

11866번: 요세푸스 문제 0

 

문제요약

• 1 부터 주어진 숫자까지의 숫자가 나열
• 다음 주어진 숫자만큼 건너 뛰면서 해당 숫자를 제거하고 출력

이전에 회전하는 큐와 비슷한 문제 접근으로 할 수 있다는 것을 알았다.
왜냐면 3번째 숫자 전까지 옮겨주고, 3번째 숫자를 제거 한뒤 이를 기록하는 방식으로 접근했다면 쉬웠을 것이다.
하지만, 해당 방법은 추후에 생각해 낸 것이고 현재는 규칙을 찾아 시도했다.

1 2 3 4 5 6 7
이라고 가정하면,
1. 오른쪽으로 계속 진행하는 경우, 이경우는 제거 인덱스를 지속적으로 늘려주면된다.
2. 오른쪽에서 다시 처음으로 돌아오는 경우, 이경우의 인덱스를 알아내는 작업이 필요했다.

제거하는 인덱스의 경우, 건너뛰는 크기(step - 1) 씩한 인덱스이다.

지워지는 숫자	끝 (지우는 인덱스)  +2씩	size
3	2	7
6	4	6
2	6 % 5 = 1  ( 여기서 + 2 시작)	5
7	3	4
5	5 % 3 = 2	3
	4 % 2 = 0	2

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

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        LinkedList<Integer> dq = new LinkedList<>();

        String[] row = reader.readLine().split(" ");
        int repeat = Integer.parseInt(row[0]);
        int step = Integer.parseInt(row[1]);

        sb.append("<");

        // queue 만들기 1 2 3 4 5 6 7
        for (int i = repeat; i >= 1; i--) {
            dq.push(i);
        }

        int tempStep = 0;

        // repeat 수만큼 반복
        for (int i = 1; i <= repeat; i++) {

            if(i == repeat){
                sb.append(dq.get(0));
                break;
            }

            tempStep += step - 1;
            if(tempStep < dq.size()){
                sb.append(dq.get(tempStep) + ", ");
                dq.remove(dq.get(tempStep));

            } else {
                tempStep = tempStep % dq.size();
                sb.append(dq.get(tempStep) + ", ");
                dq.remove(dq.get(tempStep));
            }
        }
        sb.append(">");
        System.out.println(sb);
    }
}