백준 2164 - 카드2

문제 파악

카드가 1부터 N까지 차례대로 쌓여있다.
1. 가장 위에 있는 카드를 버린다.
2. 그다음으로 가장 위에 있는 카드를 맨 밑으로 옮긴다.
3. 반복한다.
=> 가장 마지막에 남는 카드는?

큐의 FIFO(선입선출) 성질을 이용해 풀 수 있다.
가장 위에 있는 카드(가장 먼저 큐에 들어온 수)를 꺼낸다(버린다).
그 다음 카드를 꺼내고 제일 뒤(제일 밑)에 넣는다.

풀이

1. N의 값을 입력받는다.
2. 1부터 N까지 차례대로 큐에 넣는다.
3. 큐의 길이가 1이 될 때까지 반복한다.
   a. 첫 번째 카드 꺼내기
   b. 다음 카드 꺼내고 다시 삽입하기

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 카드_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        Queue<Integer> queue = new LinkedList<>();

        //1부터 N까지 큐에 삽입
        for (int i=1; i<=N; i++) {
            queue.add(i);
        }

        //카드가 한 장 남을 때까지 반복
        while (queue.size() > 1) {
            //가장 위에 있는 카드 버리기
            queue.poll();
            //그 다음 위에 있는 카드 빼서 다시 삽입
            queue.add(queue.poll());
        }

        //마지막 남은 한 장 출력
        System.out.println(queue.poll());
    }
}