[큐] 백준 2164번

 

문제

N장의 카드가 존재 (순서가 순차적으로 카드개수만큼 존재)
1. 1에서 N까지 번호가 존재
2. 아래 동작으로 계속 반복 후 마지막 수를 출력 
( 순서 )
    > 가장 위에 있는 카드를 바닥에 버림
    > 그다음 가장 위에있는 카드를 마지막으로 옮김
    > 이걸 반복

정수 N ( 1 <= N <= 500,000 )이 주어진다.

 

문제분석

• 가장 위에있는 카드를 가장 마지막으로 이동 시키는 작업 ( -> Queue의 이해도 확인 )
• 선입선출을 생각하여 문제 풀기

 

슈도코드

N개 입력 받기
for( 카드의 개수 ){
    큐에 카드 저장
}

while( 카드 1장이 남을때까지 ){
     맨위의 카드를 버림
     맨위의 카드를 가장 아래의 카드 밑으로 이동
}

마지막으로 남은 카드 출력

 

구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class App {
    public static void main(String[] args) throws Exception {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(buf.readLine());
        
        Queue<Integer> q = new LinkedList<>();

        for (int i =1; i<= size; i++){
            q.add(i);
        }

        while(q.size() > 1){
            q.poll();
            q.add(q.poll());
        }
        System.out.println(q.poll());
        
    }
}