백준 28066 (타노스는 요세푸스가 밉다) <Deque, Queue 최적화>

문제

28066번: 타노스는 요세푸스가 밉다

원형태로 앉아 있는 N 마리의 청설모가 있다.

N 마리의 청설모는 각각 1 부터 N까지 번호가 매겨져 있다.

여기서 맨 첫번째 청설모를 제외한  2 ~ K 번째 청설모를 모두 제거한다. 

제거한 후 청설모의 수가 2 이상이면 첫번째 청설모의 오른쪽에 있는 청설모가 첫번째 청설모가 된다.

 

청설모의 수가 K보다 작으면 첫번째 청설모를 제외한 나머지 청설모를 모두 제거한다.

---

단순한 원형큐 문제였지만, 큐를 사용했을 경우 큐의 맨 앞에 숫자를 삽입하는것이 시간이 걸렸다.

따라서 덱을 사용하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

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

        Deque<Integer>d = new ArrayDeque<>();

        for (int i = 1; i <= n; i++) {
            d.addLast(i);
        }

        while(d.size() >= k){
            d.addLast(d.pollFirst());
            for(int i=1;i<k;i++)
                d.pollFirst();
        }
        System.out.println(d.peekFirst());
    }
}

여기서 Deque, Queue는 new 연산자를 사용해 구현할 때 ArrayDeque 또는 LinkedList를 사용할 수 있다.

Queue<Integer>q = new ArrayDeque<>();
Queue<Integer>q = new LinkedList<>();

Deque<Integer>d = new ArrayDeque<>();
Deque<Integer>d = new LinkedList<>();

결론 부터 얘기하면 앞뒤에 원소를 삽입 삭제하는 것은 ArrayDeque이 빠르고

중간에 원소를 삽입하거나 삭제하는 것은 LinkedList가 좋다.

 

하지만 중간에 원소를 삽입, 삭제하는 것은 굳이 큐나 덱을 사용할 필요가 없으므로

웬만해서 큐나 덱을 사용하려면 ArrayDeque를 사용하자