[BaekJoon] 18115번 - 카드 놓기 [Java][C++]

문제 링크

---

1. 문제 풀이

Solved.ac에서 팽귄과 함께 마작을 프로필 배경을 획득할 수 있는 문제로 덱 자료구조를 활용하면 해결할 수 있다.

주어진 수열 $A$ 를 적용한 결과가 $1$ 부터 $N$ 까지의 순서가 되므로 이를 역순으로 탐색하며 초기 카드 상태를 찾아야한다. 초기 카드 상태를 담을 덱을 선언한 후 역순으로 탐색하며 1번 기술이면 덱의 앞에 카드를 삽입하면 되며, 2번 기술이면 덱의 앞에서 카드 하나를 꺼내고 카드를 삽입 후 다시 꺼냈던 카드를 넣으면 되며, 3번 기술이면 덱의 뒤에 카드를 삽입하면 된다.

예를 들어 예제 입력 2의 경우 역순인 1 -> 2 -> 3 -> 3 -> 2 순서로 기술을 적용하면 되며 첫 번째 기술이 1번 기술이므로 덱의 앞에 1을 삽입하면 된다. 다음 기술은 2번 기술로 덱의 앞에서 1을 잠시 꺼내고 덱의 앞에 2를 삽입한 후 꺼냈던 1을 다시 덱의 앞에 삽입하면 된다. 덱에는 1, 2가 순서대로 들어있다. 다음 기술과 다다음 기술은 3번 기술로 덱의 뒤에 삽입하면 되며, 덱에는 1, 2, 3, 4가 순서대로 들어있다. 마지막 기술은 2번 기술로 적용 시 덱에는 1, 5, 2, 3, 4가 순서대로 들어있게 되며 이 덱에 대해 주어진 기술을 순서대로 적용시 1, 2, 3, 4, 5가 잘 나오는 것을 볼 수 있다.

---

2. 코드

1. 풀이 [Java]

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

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

        Deque<Integer> dq = new ArrayDeque<>();

        st = new StringTokenizer(new StringBuilder(br.readLine()).reverse().toString());
        for (int i = 1; i <= n; i++) {
            int x = Integer.parseInt(st.nextToken());

            if (x == 1) {
                dq.offerFirst(i);
            } else if (x == 2) {
                int tmp = dq.pollFirst();
                dq.offerFirst(i);
                dq.offerFirst(tmp);
            } else {
                dq.offerLast(i);
            }
        }

        while (!dq.isEmpty()) {
            sb.append(dq.pollFirst()).append(" ");
        }

        System.out.println(sb);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    deque<int> dq;

    vector<int> v(n);
    for (int& x : v) cin >> x;
    reverse(v.begin(), v.end());

    for (int i = 0; i < n; i++) {
        if (v[i] == 1) {
            dq.push_front(i + 1);
        } else if (v[i] == 2) {
            int tmp = dq.front();
            dq.pop_front();
            dq.push_front(i + 1);
            dq.push_front(tmp);
        } else {
            dq.push_back(i + 1);
        }
    }

    for (int x : dq) {
        cout << x << ' ';
    }
}

---