[Java] BOJ 2164 카드2

문제 

문제 링크 https://www.acmicpc.net/problem/2164

• N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
• 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
• 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
• N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.
• 첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.
• 첫째 줄에 남게 되는 카드의 번호를 출력한다.

아이디어

• 큐에 넣어서 값을 빼고 다시 넣고 반복해서 큐의 사이즈가 1이 될때 While문을 종료하고 남은 값을 출력했다. 
  
  

겪은 시행착오

• 처음에는 큐를 생각하지 못하고 While문에 조건에 조건을 달아서 구현으로 풀어보려했지만.... 생각대로 되지 않아 결국 큐로 풀게 되었다... ㅜㅜ

큐를 좀 더 빨리 생각해냈더라면.....

코드

import java.io.*;
import java.util.*;

public class BOJ2164 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        // 큐 사용
        Queue<Integer> q = new LinkedList<>();

        // 큐 값에 순서대로 숫자를 넣음
        for(int i = 1; i <= N; i++){
            q.offer(i);
        }

        // 큐에 남은 숫자가 한개가 되면 While문 종료
        while(true){
            if(q.size() == 1){
                break;
            }

            // 처음 숫자 꺼내기
            q.poll();
            // 다음 숫자를 꺼내서 저장 후
            int n = q.poll();

            // 다시 뒤에 저장
            q.offer(n);
        }

        System.out.println(q.poll());
    }
}