[BaekJoon] #5397 - 키로거 [Java][C++]

문제 링크

---

1. 아이디어

주어진 입력으로 비밀번호를 알아내야 하는 문제로 현재 커서의 앞쪽에 위치한 문자들을 저장하는 덱과 커서 뒤쪽에 위치한 문자들을 저장하는 덱 두 개를 활용해서 해결했다.

주어진 입력의 문자들을 순회하며 해당 문자가 -이면 앞 덱의 rear의 원소를 제거하는 것으로 동일한 효과를 볼 수 있다. 화살표 입력의 경우 각각 앞 덱의 rear의 문자를 뒤 덱의 front로 옮기거나, 뒤 덱의 front의 원소를 앞 덱의 rear로 옮기면 된다. 비밀번호에 포함된 문자면 앞 덱의 rear에 삽입하면 된다.

주어진 명령어를 모두 수행하면 앞 덱의 front부터 rear, 이후 뒤 덱의 front부터 rear를 순서대로 출력하면 비밀번호를 얻을 수 있다.

---

2. 복잡도

접근	시간	공간
풀이	$O(T \times N)$	$O(N)$

($T$ = 테스트 케이스 수, $N$ = 케이스당 s의 길이의 최댓값)

---

3. 코드

풀이 [Java][C++]

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();

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            Deque<Character> f = new ArrayDeque<>();
            Deque<Character> b = new ArrayDeque<>();

            String s = br.readLine();
            for (char c : s.toCharArray()) {
                if (c == '-') {
                    if (!f.isEmpty()) f.pollLast();
                } else if (c == '<') {
                    if (!f.isEmpty()) b.offerFirst(f.pollLast());
                } else if (c == '>') {
                    if (!b.isEmpty()) f.offerLast(b.pollFirst());
                } else {
                    f.offerLast(c);
                }
            }

            while (!f.isEmpty()) {
                sb.append(f.pollFirst());
            }
            while (!b.isEmpty()) {
                sb.append(b.pollFirst());
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
}

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

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

    int t;
    cin >> t;

    while (t--) {
        deque<char> f, b;

        string s;
        cin >> s;

        for (char c : s) {
            if (c == '-') {
                if (!f.empty()) f.pop_back();
            } else if (c == '<') {
                if (!f.empty()) {
                    b.push_front(f.back());
                    f.pop_back();
                }
            } else if (c == '>') {
                if (!b.empty()) {
                    f.push_back(b.front());
                    b.pop_front();
                }
            } else {
                f.push_back(c);
            }
        }

        while (!f.empty()) {
            cout << f.front();
            f.pop_front();
        }
        while (!b.empty()) {
            cout << b.front();
            b.pop_front();
        }
        cout << '\n';
    }
}

---