[백준]2164번. 카드2 (JAVA)

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

---

문제

---

풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

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

        for(int i = 1; i < n+1; i++){
            queue.add(i);
        }

        int check = 1;

        while (queue.size() > 1){
            if(check % 2 == 1){
                queue.poll();
            }else{
                int temp = queue.poll();
                queue.add(temp);
            }
            check++;
        }

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

가장 먼저 들어간 것이 먼저 나오는 선입선출 구조를 띄고 있기 때문에 큐 자료구조를 사용했다.

 

추가적으로 반복 횟수에 따라 동작이 달라지므로 주기가 2인 동작을 처리하기 위해 check라는 변수를 두어 처리했다. 

다만 실제 문제 제출본은

       while (queue.size() > 1){
            if(check == 1){
                queue.poll();
                check--;
            }else{
                int temp = queue.poll();
                queue.add(temp);
                check++;
            }
        }

로 제출했다. 이유는 위의 풀이대로면 한번의 while반복마다 %2, ==1, ++로 3번의 연산이 들어가게 된다. 하지만 아래와 같이 수정하면 ==1, ++ or --로 2번의 연산으로 처리가 가능하기 때문이다. 사소하지만 언제나 중요하게 처리하는 습관을 들여야할 것 같다.

또한 이 문제 역시 for(int i = 1; i <=n  or i <n+1; i++)로 처리해야 함에 주의하자.