[백준] 2161번 : 카드1 – JAVA [자바]

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

2161번: 카드1

 

---

• 문제

 

 

---

• 문제 풀이

백준 2161번 카드1은 브론즈 1 난이도의 자료구조 및 구현 문제였다. 이 문제에서는 n장의 카드가 주어진다. 이 카드들은 제일 위에서부터 1부터 n까지 있다. 즉, 1이 맨 위에 있고 n이 맨 밑에 있다는 것이다. 이 카드들은 카드가 1장이 될 때까지 맨 위에 있는 카드를 먼저 버린다. 그리고 맨 위에 있는 카드를 맨 밑에 둔다. 이 절차를 카드가 1장이 될 때까지 지속한다. 카드가 1장이 되면 버린 카드들을 순서대로 출력하고 마지막에 남아있는 카드를 출력하면 된다.

 

이 문제는 덱과 큐를 이용해서 풀 것이다. 우선 덱은 처음에 가지고 있는 카드들이라고 정의하겠다. 따라서 처음에는 1부터 n까지 있다. 그리고 큐는 버린 카드들을 저장하겠다.

 

우선 카드가 1장이 될 때까지 해야 하니까 while-loop을 이용하겠다. 카드가 1장이 될 때까지 해야 하니까 다음과 같이 코드를 쓸 수 있다.

while (deque.size() > 1) {
	//code
}

 

이제 이 while-loop안에 어떤 코드를 써야 하는지 보겠다.

 

처음에 맨 위에 있는 카드를 버린다. 따라서 덱에서 맨 위에 있는 카드를 큐에 추가하면 된다.

queue.add(deque.removeFirst());

 

그다음엔 덱 맨 위에 있는 카드를 덱 맨 밑으로 넣으면 된다.

deque.addLast(deque.removeFirst());

 

이렇게 반복을 해주고 큐에 있는 카드들과 마지막에는 덱에 남아있는 카드 1장을 출력해주면 끝난다.

 

---

• 코드

 

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));
        int n = Integer.parseInt(br.readLine());
        Deque<Integer> deque = new LinkedList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            deque.addLast(i);
        }
        while (deque.size() > 1) {
            queue.add(deque.removeFirst());
            deque.addLast(deque.removeFirst());
        }
        StringBuilder sb = new StringBuilder();
        for (int i : queue) {
            sb.append(i + " ");
        }
        sb.append(deque.remove());
        System.out.print(sb);
    }
}

---

• 후기

이 문제는 덱과 큐를 이용해서 가볍게 풀 수 있는 문제였다.