[BOJ]백준5397번: 키로거(JAVA)

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

문제

창영이는 컴퓨터에 키 입력을 하면 입력한 키를 바탕으로 비밀번호를 알아 내고 싶어한다.

• 길이가 L인 문자열의 길이는 최대 1,000,000이다.
• ← 를 입력하면 현재 문자열 커서에서 한 칸 왼쪽으로 가서 문자를 입력한다.
• → 를 입력하면 현재 문자열 커서에서 한 칸 오른쪽으로 가서 문자를 입력한다.

풀이

• 문자열의 크기가 1,000,000 이므로 배열로 해결하기가 어렵다.
• 스택을 활용하여, 선형시간 문제를 해결할 수 있는 알고리즘을 설계한다.
• 스택 두 개를 만들고, 스택 두 개의 중간 지점을 커너로 간주한다.
• 문자입력: 왼쪽 스택에 원소를 삽입한다.
• BackSpace 입력 : 왼쪽 스택에서 문자를 삭제한다.
• ← 입력 : 왼쪽 스택에서 오른쪽 스택으로 원소를 이동한다.
• → 입력 : 오른쪽 스택에서 왼쪽 스택으로 원소를 이동한다.
  

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

class Baekjoon_5397 {
    public static void main(String[] args) throws IOException {
        // BufferedREader 를 통해 입력 값 얻기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        String[] input;
        // Test케이스의 갯수를 입력받는 코드
        // String 배열의 input 생성

        for(int i=0;i<T;i++) {
            Stack<String> left = new Stack<>();
            Stack<String> right = new Stack<>();
            input = br.readLine().split("");

            for (String str : input) {
                switch (str) {
                    case "<":
                        if(!left.isEmpty()){
                            right.push(left.pop());
                        }
                        break;


                    case ">":
                        if (!right.isEmpty()) {
                            left.push(right.pop());
                        }
                        break;

                    case "-":
                        if (!left.isEmpty()) {
                            left.pop();
                        }
                        break;

                    default:
                        left.push(str);
                }
            }


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

    }
}