[백준/Silver III] 카드 놓기 - 18115

• ((LinkedList) dq).add(1, card): 원래 본 코드를 사용하여 덱의 두 번째 위치에 삽입하려 했지만, 해당 연산은 LinkedList 내부 구조상 최악의 경우 N제곱의 시간복잡도를 초래할 수 있어서 '시간 초과' 발생했습니다. (N번 반복하면서 N의 위치에 삽입하기 때문)
• 따라서 1번째 요소 임의제거 -> card를 앞에 삽입 -> 다시 1번째 요소를 되돌리는 방식으로 수정하여 문제를 해결했습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class B18115 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] a = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        br.close();

        Deque<Integer> dq = new LinkedList<>();
        // 기술 -> 덱 만들기
        for (int i = n-1; i >= 0; i--) {
            int card = n-i;
            int skill = a[i];
            if (skill == 1) {
                dq.addFirst(card);
            } else if (skill == 2) {
                // 최악의 경우 N**2: ((LinkedList<Integer>) dq).add(1, card);
                int first = dq.pollFirst();
                dq.addFirst(card);
                dq.addFirst(first);
            } else if (skill == 3) {
                dq.addLast(card);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int x : dq) {
            sb.append(x).append(" ");
        }
        System.out.println(sb.toString().trim());
    }
}