[백준/2164]카드2

반응형

[문제]

n장의 카드가 있고, 각각의 카드는 차례로 1부터 n까지의 번호가 붙어있다. 1번 카드가 제일 위에, n번 카드가 제일 아래인 상태로 순서대로 카드가 놓여있다. 카드가 한 장만 남을 때까지 다음과 같은 연산을 반복한다.

제일 위에서부터 1,2,3,4 의 순서로 놓여있을 때 1을 버리면 2,3,4 가 남는다. 여기서 2를 제일 아래로 옮기면 3,4,2가 된다. 3을 버리면 4,2가 되고 4을 밑으로 옮기면 2,4가 된다. 마지막으로 2를 버리고 나면 남는 카드6는 4가 된다. 이때 n(1 <= n <= 500,000)개의 카드가 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

ex.
입력값 = 6
결과 = 4

[풀이]

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        Queue<Integer> queue = new LinkedList<>(); // Queue 선언
        int n = sc.nextInt(); // 정수 n 받기
        int num = 1; //1부터 시작
        for(int i=1;i<=n;i++){
            queue.add(i); //1부터 차례대로 queue에 넣기
        }
        if(!queue.isEmpty()){
            while(queue.size()>1){ //마지막 1개가 남을때까지
                queue.poll();
                queue.add(queue.poll());
            }
            System.out.println(queue.poll());
        }
    }
}