[BOJ] 2164. 카드2(Queue).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

Queue를 사용하면 단순하게(?) 풀리는 문제다.

#. Code v1: Queue

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue;   public class BOJ2164 {       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));           Queue<Integer> q = new LinkedList<>();         int N = Integer.parseInt(br.readLine());         for (int i = 1; i <= N; i++)             q.add(i);           while (q.size() != 1) {             // 제일 위에 있는 카드를 바닥에 버린다             q.poll();             // 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로             q.add(q.poll());         }           System.out.println(q.poll());     }   } Colored by Color Scripter

cs

#. Code v2 : 원형 Queue 구현

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Deque;   public class BOJ2164_v2 {       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));           int N = Integer.parseInt(br.readLine());         int arr[] = new int[N];         for (int i = 0; i < N; i++)             arr[i] = i+1;           int front = 0;         int rear = N-1;                  while (front != rear) {             // 제일 위에 있는 카드를 바닥에 버린다             arr[front++] = 0;             if(front >= N) front -= N;             // 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로             int tmp = arr[front];             arr[front++] = 0;             if(front >= N) front -= N;             rear++;             if(rear >= N) rear -= N;             arr[rear] = tmp;         }           System.out.println(arr[rear]);     }   } Colored by Color Scripter

cs

#. Code v3: 규칙

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Deque;   public class BOJ2164_v3 {       public static void main(String[] args) throws IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));           int N = Integer.parseInt(br.readLine());         // 1. N과 가장 가까운 2의 제곱수를 찾기         // 2. N - (그 제곱수) * 2 가 답         int n = 1;         while(n < N) {             n *= 2;         }         // 여기서 n은 N보다 큰 2의 제곱수         n /= 2;         if(N == 1)              System.out.println(1);         else             System.out.println((N-n) * 2);     }   } Colored by Color Scripter

cs