[210916] 백준 5397번 문제 풀이 / 키로거

 

 

 

문제의 핵心

1. 문자열 크기가 최대 1,000,000이므로 시뮬레이션 방식으로는 문제를 해결할 수 없다.
2. 스택을 활용하여 선형시간 문제를 해결할 수 있는 알고리즘을 설계한다.
3. 스택 두 개를 만들고, 스택 두 개의 중간 지점을 커너(Cursor)로 간주한다. 
4. 문자 입력 : 왼쪽 스택에 원소를 삽입한다.
5. - 입력 : 왼쪽 스택에서 원소를 삭제한다.
6. < 입력 :  왼쪽 스택에서 오른쪽 스택으로 원소를 이동한다.
7. > 입력 : 오른쪽 스택에서 왼쪽 스택으로 원소를 이동한다.

 

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

public class Q5_5397 {

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

  }

}