자료구조 5/12 - LinkedList

연관문제

요세푸스 문제 - 백준 1158번

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;

public class Linked {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = (br.readLine()).split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);
        int[] answer = new int[N];

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

        int cur = 0;
        int size = N;
        while (size > 0) {
            cur = (cur + K - 1) % size;  // LinkedList 에서는 값을 제거하면 뒤에 있는 원소가 당겨져 와서 1칸 SHIFT 되는 효과가 있다.
            answer[N - size] = linkedList.remove(cur);
            size--;
        }

        System.out.println(Arrays.toString(answer).replace("[", "<").replace("]", ">"));
    }
}

LinkedList 를 이용해서 값을 제거할 때, 자동으로 뒤에 있는 원소가 비어있는 자리로 당겨져 오기 때문에 1칸 shift 되는 효과가 있다는 점. 그래서 K 칸씩 값 체크가 아닌 K - 1 칸 씩 값 체크를 한다는 점만 특이했다.