[백준] 18115번 : 카드 놓기 – JAVA [자바]

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

18115번: 카드 놓기

 

---

• 문제

 

 

---

• 문제 풀이

백준 18115번 카드 놓기는 실버 3 난이도의 자료 구조 및 덱 문제이다. 

 

이 문제에서는 길이가 N인 수열이 주어진다. 이 수열에서는 N개의 기술들이 주어진다. 이때, 기술들은 다음과 같다.

 

1. 제일 위의 카드 1장을 바닥에 내려놓는다.
2. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.
3. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.

 

이 N개의 기술들을 쓰고 난 이후에 놓여 있는 카드들은 1, 2, ... , N이라고 한다. 이때, 처음 카드의 상태를 출력하면 된다.

 

우선, 이 문제에서는 카드의 마지막 상태인 1, 2, ... , N 부터 처음의 카트 상태를 구해야 한다. 따라서, 기술들이 주어졌을 때, 이것을 반대인 역순으로 처리를 해줘야 한다.

 

이 문제는 덱을 이용해서 풀 수 있다. 덱은 양쪽에서 삽입과 삭제가 가능한 구조이다. 자세하게 알고 싶다면 이 링크를 참고하면 되겠다.

 

우선, 첫 번째 기술이 주어졌을 때, 덱 맨 앞에 추가하면 된다. 왜냐하면, 1은 제일 위에 있는 카드를 내려놓기 때문이다.

 

그리고, 두 번째 기술이 주어졌을 때는 덱 맨 앞에서 두 번째 위치에 추가해 주면 된다. 덱은 두 번째 위치에 따로 추가하는 기능이 없기 때문에, 이미 있는 첫 번째 카드를 제거하고, 그다음에 물건을 추가한다. 그리고, 제거한 카드를 맨 앞에 다시 넣어주면 된다.

 

세 번째 기술이 주어졌을 때는 덱 맨 뒤에 추가해 주면 된다.

 

이 과정이 끝난다면, 덱 맨 앞에서부터 있는 카드들을 출력해 주면 된다.

 

---

• 코드

 

import java.io.*;
import java.time.LocalTime;
import java.util.*;

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

        // 카드의 수 N 입력
        int n = Integer.parseInt(br.readLine());

        // 역순으로 주어진 기술들을 StringTokenizer를 사용하여 역순으로 파싱하여 Deque에 저장
        StringTokenizer st = new StringTokenizer(new StringBuilder(br.readLine()).reverse().toString());
        Deque<Integer> deque = new LinkedList<>();

        // N번의 기술에 따라 카드들을 처리
        for (int i = 1; i <= n; i++) {
            int num = Integer.parseInt(st.nextToken());

            // 기술에 따라 카드를 Deque의 앞쪽, 뒤쪽에 추가 또는 이동
            if (num == 1) {
                deque.addFirst(i);
            } else if (num == 2) {
                int top = deque.removeFirst();
                deque.addFirst(i);
                deque.addFirst(top);
            } else {
                deque.addLast(i);
            }
        }

        // 최종적으로 Deque에 있는 카드들을 순서대로 StringBuilder에 추가
        StringBuilder sb = new StringBuilder();
        while (deque.size() != 0) {
            sb.append(deque.removeFirst() + " ");
        }

        // 결과 출력
        System.out.println(sb);
    }
}