[자바] 백준 2164번 카드2

https://www.acmicpc.net/problem/2164

 

[문제 이해]

문제 그대로 카드가 순서대로 있을 때 하나의 카드가 남을 때까지 가장 위의 카드는 버리고, 두 번째 카드는 가장 아래에 있는 카드 밑으로 옮기면서 마지막으로 남은 카드의 숫자를 출력하면 되는 문제였다.

 

[문제 풀이]

deque를 사용해서 문제를 풀어봤다면 어렵지 않게 풀 수 있는 문제였다. 먼저 입력 받은 숫자까지의 카드를 deque에 저장하기 위해 offerLast()함수를 사용한다. 이후로는 규칙에 맞게 반복문을 돌리되, deque 내의 원소의 개수가 1개보다 많을 때까지만 돌리면 된다. 가장 앞의 카드를 버리기 위해서 removeFirst()함수를 사용하고 한 번 더 두 번째 카드를 뒤로 보내기 위해 앞에서 removeFirst()함수로 꺼내고 뒤에 추가하기 위해 offerLast()함수를 사용하기만 하면 해결된다. 마지막으로 남은 원소는 0번째 인덱스에 있으므로 deque.peekFirst()를 하면 답을 맞출 수 있다.

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Deque<Integer> deque = new ArrayDeque<>();
        for(int i = 0; i < n; i++){
            deque.offerLast(i+1);
        }

        while(deque.size() > 1){
            deque.removeFirst();
            deque.offerLast(deque.removeFirst());
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(deque.peekFirst()));
        bw.flush();
        bw.close();
    }
}