문제 출처

단계별로 풀어보기 > 스택 큐 덱 > 카드 2
https://www.acmicpc.net/problem/2164

문제 설명

N장의 카드가 있을 때, 1번 카드가 가장 위, N번 카드가 가장 아래에 있다.
이 때, 다음1,2번 같은 과정을 반복하여 카드가 1장이 남을 때까지 제거한다.
1. 카드를 제일 위에서 제거
2. 카드를 제일 위에서 뽑은 뒤 맨 아래에 삽입

접근 방법

큐를 이용하여 각 횟차에 따라(홀수번 행동, 짝수번 행동) poll을 하거나, poll하여 다시 삽입하거나 반복하여 카드가 1장 남을 때까지 반복한다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class 카드2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

        for(int i = 0; i<N; i++){
            q.offer(i+1);
        }

        int count = 1;
        while(q.size() != 1){
            if(count % 2 == 1){
                q.poll();
            }else if (count % 2 == 0){
                int k = q.poll();
                q.offer(k);
            }
            count++;
        }
        bw.write(String.valueOf(q.poll()));
        bw.flush();
        bw.close();
        br.close();
    }
}

Review

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class 카드2_review {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        int N = Integer.parseInt(br.readLine());
        for(int i = 0; i<N; i++){
            q.offer(i+1);
        }

        int count = 1;
        while(q.size() != 1){
            if(count % 2 == 1){
                q.poll();
            } else {
                int k = q.poll();
                q.offer(k);
            }
            count++;
        }

        bw.write(String.valueOf(q.poll()));
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

처음에 q.size() != 1 설정을 잘 못잡아서 반복문이 진행이 안되었었다. 해당 부분에 주의하자.

문제푼 흔적

Review