항해99 29일차 TIL( 에디터 / 백준)

문제         

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

1 번째 시도   

• 스택 문제를 골라 풀기 시작했지만 처음 봤을 때 스택 문제라고 생각이 안들었습니다.
  • 다른 풀이)
    • ArrayList에 문자열을 담는다. 
    • 커서위치를 cInd라는 변수에 담는다
    • cInd가 가르키는 곳에 추가하거나 삭제한다.

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine(); 
        int n = Integer.parseInt(br.readLine()); 

        StringBuilder list = new StringBuilder(input);
        int cInd = input.length(); 

        for(int i = 0; i < n; i++) {
            String line = br.readLine();
            String[] lines = line.split(" ");
             
            if(lines[0].equals("P")) {
                String addX = lines[1];
                list.insert(cInd, addX);
                cInd++; 
            }
            else if(lines[0].equals("L")) { 
               if(cInd > 0) cInd--; 
            }
            else if(lines[0].equals("D")) { 
                if(cInd < list.length()) cInd++;
            }
            else if(lines[0].equals("B")) { 
                if(cInd > 0) {
                    list.deleteCharAt(cInd - 1);
                    cInd--; 
                }
            }
        }
        
        System.out.println(list.toString());
    }
}

2 번째 시도  

• 성공은 했지만 시간이 1576ms로 남들보다 오래 걸린 편이다
• 내가 생각하기엔 이 문제는 구현보다는 시간에 초점이 맞혀져 있다.
• StringBuilder의 마지막삽입은 O(1)이지만 중간삽입은O(n−k)이다.
  • 삽입위치에서부터 끝 위치까지 저부 한 칸씩 밀어야 하기 때문에
• Stack의 연산은 O(1)이다.
• Stack을 사용하여 리팩토링
• 커서 왼쪽 요소들 leftstack, 커서 오른쪽 요소들 rightstack

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
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(int i = 0; i < str.length(); i++)
            leftstack.push(str.charAt(i));
 
        int cnt = Integer.parseInt(br.readLine());
 
        for(int i = 0; i < cnt; i++){
            String order = br.readLine();
            switch(order.charAt(0)){
                case 'L':
                    if(!leftstack.isEmpty()) rightstack.push(leftstack.pop());
                    break;
                case 'D':
                    if(!rightstack.isEmpty()) leftstack.push(rightstack.pop());
                    break;
                case 'B':
                    if(!leftstack.isEmpty()) leftstack.pop();
                    break;
                case 'P':
                    leftstack.push(order.charAt(2));
            }
        }
 
        while(!leftstack.isEmpty())
            rightstack.push(leftstack.pop());
 
        StringBuilder sb = new StringBuilder();
 
        while(!rightstack.isEmpty())
            sb.append(rightstack.pop());
 
        System.out.print(sb);
    }
}