[백준, 2164] 카드2

문제

 

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

 

다음 동작을 카드가 한 장 남을 때까지 반복

-> 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

 

 

---

입력 예시가 6이면 카드는 위에서부터 1,2,3,4,5,6 으로 쌓여있는 상태이다.

1을 버리고 2를 제일 밑으로 보내는 식으로 반복하면

 

1) 3,4,5,6,2

2) 5,6,2,4

3) 2,4,6

4) 6,4

 

마지막에 6을 버리면 정답은 4가 된다.

 

제일 위에 숫자를 버리고 제일 밑에 숫자를 추가하는 식의 동작이기 때문에 Deque를 사용하면 될 것 같다.

처음에 Deque가 떠올랐는데 생각해보니 그냥 Queue를 사용해도 poll하고 다시 넣으면 제일 뒤로 가기 때문에 더 나은 것 같다.

 

int N = Integer.parseInt(br.readLine());

Deque<Integer> deque = new LinkedList<>();

for (int i = 1; i <= N; i++) {
    deque.addFirst(i);
}

while (deque.size() > 1) {
    deque.removeLast();
    deque.addFirst(deque.removeLast());
}

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