[Java/스택] 백준 5397. 키로거

🤔 Intuition

스택 문제인게 느껴졌는데 커서 관리를 어떻게 할까 고민했다.

 

근데 동작이 왼쪽 오른쪽 백스페이스 뿐이라, 스택을 두개 쓰면 N번 루프를 한번만 돌면서 중간 지점에 커서를 유지하고, 요구 연산을 O(1) 로 수행할 수 있겠다 판단했다.

🔎 Algorithm & Complexity

* @algorithm stack
* @time O(N) -> 1144 ms
* @memory O(N) -> 311176 KB

👨🏻‍💻 Logic

단순하다. 커서 움직임에 따라 문자를 왼쪽 오른쪽 스택으로 옮겨주면 된다. 코드가 간단해서 보면 다들 이해가 쉬울 것이다.

public class BOJ_5397_키로거 {
    private static int N;
    private static StringBuilder sb = new StringBuilder();
    private static Deque<String> left = new ArrayDeque<>();
    private static Deque<String> right = new ArrayDeque<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            int length = s.length();
            String ss;
            for (int j = 0; j < length; j++) {
                ss = s.substring(j, j + 1);
                if (ss.equals("<")) {
                    // left pop
                    // right add
                    if (left.isEmpty()) {
                        continue;
                    }
                    String pop = left.pop();
                    right.push(pop);

                } else if (ss.equals(">")) {
                    // right pop
                    // left add
                    if (right.isEmpty()) {
                        continue;
                    }
                    String pop = right.pop();
                    left.push(pop);

                } else if (ss.equals("-")) {
                    // left pop
                    if (left.isEmpty()) {
                        continue;
                    }
                    left.pop();

                } else {
                    left.push(ss);
                }
            }
            while (!left.isEmpty()) {
                right.push(left.pop());
            }
            while (!right.isEmpty()) {
                sb.append(right.pop());
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
}