[백준] 2164번 카드2 (Java)

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

2164번: 카드2

---

문제

---

알고리즘

 

일단 또 바보 같은 짓했다 ! 원래 이렇게 바보 짓을 해야 더 발전할 수 있는 법 ~ 또 하나의 발전을 할 수 있다는 점 ~

바보짓하다가 메모리 초과났길래 이번에는 어떤 알고리즘으로 풀어야 하나하고 보니 드디어 나왔다. 

QUEUE

 

특징 1. 선입선출(First In First Out)

특징 2. 앞은 front, 뒤는 rear 라고 칭한다.

 

생각나는건 이 정도고 .. 좀 더 공부해서 Queue에 대한 공부도 좀 해봐야겠다. 뒷얘기가 많은 것 같길래 .. 나중에 ..

 

1. Queue 선언 

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

 

java.util 패키지에 있는 Queue와 LinkedList를 import 해서 사용한다.

 

2. Queue 데이터 삽입 : offer(), add()

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

// 1. offer()
que.offer(1);

// 2. add()
que.add(2);

 

3. Queue 데이터 추출 : poll()

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

que.offer(1);
que.add(2);

que.poll(); // 1 추출

 

4. Queue 맨 앞 데이터 확인 : peek()

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

que.offer(1);
que.add(2);

que.peek(); // 1 확인

 

5. Queue 사이즈 확인 : size()

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

que.offer(1);
que.add(2);

System.out.println(que.size()); // 2 출력

 

6. Queue 비었는지 확인 : isEmpty()

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

que.offer(1);
que.add(2);

System.out.println(que.isEmpty()); // false

 

7. Queue 특정값 삭제 : remove( value )

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

que.offer(1);
que.add(2);

que.remove(2); // 2 삭제

---

여기까지 Queue에 대해서 정리하고, 이번 문제를 어떻게 푸는지 설명하겠다.

 

1. N을 입력받고 큐에 1~N까지 저장한다.

2. 맨 앞의 수를 poll()하여 추출한다.

3. 그 다음 수도 poll()하여 추출하고 큐에 다시 add()해준다.

4. 2~3번 과정을 큐에 데이터가 1개만 남을 때까지 반복한다.

5. 큐에 남은 값을 출력한다.

 

---

코드

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

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

        int N = Integer.parseInt(br.readLine()); // 카드 개수

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

        for(int i=1; i<=N; i++){
            que.add(i);
        }

        while(que.size() > 1) {
            que.poll();
            int tmp = que.poll();
            que.add(tmp);
        }

        bw.write(que.peek() + "\n");
        bw.close();
        br.close();
    }
}