📝 문제 설명

1. N장의 카드를 입력 받는다.
2. N장의 카드: 각각의 카드는 차례로 1부터 N까지 번호가 붙어있다. 1번 카드가 제일 위, N번 카드가 제일 아래에 위치한다.
3. 다음과 같은 동작을 카드가 한 장 남을 때까지 반복한다. 1) 제일 위에 있는 카드를 버린다. 2) 그 다음으로 가장 위에 있는 카드를 최 하단 카드의 밑으로 옮긴다.

문제 링크

💡 아이디어

• ArrayDeque를 사용해서 cardSet을 구현한다.
  • Deque 인터페이스 구현 시, 공식 문서에서 ArrayDeque 사용을 권한다. 공식 문서
• 안정성을 위해서 .remove 보다는 .pollFirst를 사용한다.
  • .remove()는 덱이 비어 있을 때 NoSuchElementException을 발생시키지만, .pollFirst()는 null을 반환하므로 예외 없이 처리할 수 있다.

🛠 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

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

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

        while (cardSet.size() > 1) {
            cardSet.pollFirst();
            cardSet.addLast(cardSet.pollFirst());
        }

        System.out.println(cardSet.peek());


    }
}

⏱ 시간복잡도

• 카드는 총 N장이고, pollFirst()와 addLast() 연산은 각각 시간 복잡도 O(1)인 Deque의 메서드를 사용한다.
• 카드를 한 장 남을 때까지 반복하므로 총 N번의 연산이 수행된다.
• 따라서 전체 시간 복잡도는 O(N)이다.

✏️ 느낀 점

• 앞으로 대부분은 ArrayDeque로 구현 시도 해야겠다.
• 안정성을 위해 .poll .peek 함수를 적극 사용해야겠다.