11/19 Stack

백준 1406

• 에디터

• 아이디어

  처음 주어진 문자열 leftStack에 저장

  L : 커서 왼쪽으로 한칸 => leftStack pop() => rightStack push(), 문장의 맨앞은 무시

  D : 커서 오른쪽으로 한칸 => rightStack pop() => leftStack push()

  B : 커서 왼쪽에 있는 문자를 삭제 => leftStack pop()

  P $ : $라는 문자를 커서 왼쪽에 추가

• 문제

  한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

  이 편집기에는 ‘커서’라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

  이 편집기가 지원하는 명령어는 다음과 같다.

  package Baekjoon;
    
  import java.util.Scanner;
  import java.util.Stack;
    
    
    
  public class baek1406 {
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
            
          Stack<Character> leftStack = new Stack<>();
          Stack<Character> rightStack = new Stack<>();
            
          String str = sc.nextLine();
            
          for (char ch : str.toCharArray()) {
              leftStack.push(ch);
          }
            
          int commandNum = sc.nextInt();
          sc.nextLine();
          for (int i = 0; i < commandNum; i++) {
              String command = sc.nextLine();
              char op = command.charAt(0);
              switch(op) {
                  case 'L' :
                      if (!leftStack.empty()) {
                          rightStack.push(leftStack.pop());
                      }
                      break;
                  case 'D' :
                      if (!rightStack.empty()) {
                          leftStack.push(rightStack.pop());
                      }
                      break;
                  case 'B' :
                      if (!leftStack.empty()) {
                          leftStack.pop();
                      }
                      break;
                  case 'P' :
                      char insertChar = command.charAt(2);
                      leftStack.push(insertChar);
                      break;
              }
          }
            
          while (!leftStack.empty()) {
              rightStack.push(leftStack.pop());
          }
            
          while (!rightStack.empty()) {
              System.out.print(rightStack.pop());
          }
      }
  }
  

  맨 처음 풀었던 풀이지만, 시간초과 오류가 났다.

풀이 2

Scanner 대신 BufferedReader를 사용했지만 이번엔 게이지가 조금 올라가다가 중간에서 시간초과 오류가 났다. 찾아보니 마지막 while문 안에서 System.out.println()을 사용한데서 오류가 난것 같다. 마지막 while문에서 System.out.println 대신 StringBuilder를 이용해 append해준 다음 마지막에 한꺼번에 출력을 한다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        Stack<Character> leftStack = new Stack<>();
        Stack<Character> rightStack = new Stack<>();
        
        String str = br.readLine();
        
        for (char ch : str.toCharArray()) {
            leftStack.push(ch);
        }
        
        int commandNum = Integer.parseInt(br.readLine());
        for (int i = 0; i < commandNum; i++) {
            String command = br.readLine();
            char op = command.charAt(0);
            switch(op) {
                case 'L' :
                    if (!leftStack.empty()) {
                        rightStack.push(leftStack.pop());
                    }
                    break;
                case 'D' :
                    if (!rightStack.empty()) {
                        leftStack.push(rightStack.pop());
                    }
                    break;
                case 'B' :
                    if (!leftStack.empty()) {
                        leftStack.pop();
                    }
                    break;
                case 'P' :
                    char insertChar = command.charAt(2);
                    leftStack.push(insertChar);
                    break;
            }
        }
        
        while (!leftStack.empty()) {
            rightStack.push(leftStack.pop());
        }
        
        StringBuilder sb = new StringBuilder();
        while (!rightStack.empty()) {
            sb.append(rightStack.pop());
        }
        
        System.out.println(sb.toString());
    }
}