[알고리즘] 1406 에디터

[알고리즘] 1406 에디터

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

- 시간초과 때문에 고생했던 문제

- 검색을 해도 대부분 로직은 비슷했지만 이용하는 util이 시간을 많이 잡아먹으면 해결을 하지 못한다.

• 입력 받을 경우
1. Scanner scan = new Scanner(System.in); 을 이용하였지만 효율이 좋지 못하다.
2. BufferedReader 를 이용해 입력을 받는다.

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String def=br.readLine();

• 입력 받은 즉시 처리하면 for문의 사용을 줄일 수 있다.

 1) 명령을 입력 받아 저장한 뒤 실행

        // 4. 명령 수 만큼 입력받은 뒤 스택에 저장
        for (int i=0;i<sq_num;i++) {
            
            cmd[i] = br.readLine();
        }
 
        // 5. 명령 실행
        for(int i=0;i<sq_num;i++) {
            
            //5-1. L일 경우
            if(cmd[i].equals("L")) {
 
            //5-2. D일 경우
            }else if(cmd[i].equals("D")) {
 
            // 5-3. B일 경우
            }else if(cmd[i].equals("B")) {
 
            // 5-4. P$일 경우
            }else if(cmd[i].contains("P")) {
 
            }
            
        }

 2) 수만큼 입력받고 바로 처리 

        
        // 4. 명령 수 만큼 입력받은 뒤 스택에 저장
        while(sq_num-- > 0) {
            String cmd = br.readLine();
            //5-1. L일 경우
            if(cmd.equals("L")) {
                if(!stack.empty()) {
                    stack_R.push(stack.pop());
                }
 
            //5-2. D일 경우
            }else if(cmd.equals("D")) {
                if(!stack_R.empty()) {
                    stack.push(stack_R.pop());
                }
            // 5-3. B일 경우
            }else if(cmd.equals("B")) {
                if(!stack.empty()) {
                    stack.pop();
                }
            // 5-4. P$일 경우
            }else if(cmd.contains("P")) {
                char x = cmd.charAt(2);
                stack.push(x);
            }            
        }

• StringBuilder 이용하기

1.  String < StringBuffer < StringBuilder 순으로 성능이 좋다. 

• 코드

• 시간초과 난 코드

package algorithm_basic;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class q_1406 {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // 1. 기존 문자열 입력받기
        String defSentence=br.readLine();
 
        // 2. 입력받은 기존 문자열 스택에 담기
        Stack<Character> stack = new Stack<>();
        Stack<Character> stack_R = new Stack<>();
        
        for(int i=0;i<defSentence.length();i++) {
            stack.push(defSentence.charAt(i));
        }        
        
        // 3. 명령 수 입력받고 명령 저장할 스택 생성
        int sq_num=Integer.parseInt(br.readLine());
        String[] cmd = new String[sq_num];
 
        
        // 4. 명령 수 만큼 입력받은 뒤 스택에 저장
        for (int i=0;i<sq_num;i++) {
            
            cmd[i] = br.readLine();
        }
        
        System.out.println(calc(sq_num, cmd, stack, stack_R));
 
    }
 
    public static String calc(int sq_num, String[] cmd, Stack<Character> stack, Stack<Character> stack_R) {
        
        // 5. 명령 실행
        for(int i=0;i<sq_num;i++) {
            
            //5-1. L일 경우
            if(cmd[i].equals("L")) {
                //왼쪽 스택이 안 비었을 경우
                if(!stack.empty()) {
                    //오른쪽 스택에 가장 끝 문자 넣기
                    stack_R.push(stack.peek());
                    //왼쪽 스택에서 가장 끝 문자 빼기
                    stack.pop();
                }
 
            //5-2. D일 경우
            }else if(cmd[i].equals("D")) {
                //오른쪽 스택이 안비었을 경우
                if(!stack_R.empty()) {
                    //왼쪽 스택에 가장 끝 문자 넣기
                    stack.push(stack_R.peek());
                    //오른쪽 스택에서 가장 끝 문자 빼기
                    stack_R.pop();
                }
            // 5-3. B일 경우
            }else if(cmd[i].equals("B")) {
                if(!stack.empty()) {
                    stack.pop();
                }
            // 5-4. P$일 경우
            }else if(cmd[i].contains("P")) {
                //문자를 가져온다
                char x = cmd[i].charAt(2);
                //왼쪽 스택에 넣는다.
                stack.push(x);
            }
            
        }
        //왼쪽, 오른쪽 스택 붙이기
        stack.addAll(stack_R);
        
        String s_stack="";
        //스택에서 꺼내와 정렬하기
        for(int i=0;i<stack.size();i++) {
            s_stack+=stack.elementAt(i);
        }
        
        return s_stack;
    }
 
}
 

• 고친 코드

package algorithm_basic;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class q_1406_3 {
 
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 1. 기존 문자열 입력받기
        String def=br.readLine();
 
        // 2. 입력받은 기존 문자열 스택에 담기
        Stack<Character> stack = new Stack<>();
        Stack<Character> stack_R = new Stack<>();
        
        for(int i=0;i<def.length();i++) {
            stack.push(def.charAt(i));
        }        
        
        // 3. 명령 수 입력받고 명령 저장할 스택 생성
        int sq_num=Integer.parseInt(br.readLine());
        
 
        
        // 4. 명령 수 만큼 입력받은 뒤 스택에 저장
        while(sq_num-- > 0) {
            String cmd = br.readLine();
            //5-1. L일 경우
            if(cmd.equals("L")) {
                if(!stack.empty()) {
                    stack_R.push(stack.pop());
                }
 
            //5-2. D일 경우
            }else if(cmd.equals("D")) {
                if(!stack_R.empty()) {
                    stack.push(stack_R.pop());
                }
            // 5-3. B일 경우
            }else if(cmd.equals("B")) {
                if(!stack.empty()) {
                    stack.pop();
                }
            // 5-4. P$일 경우
            }else if(cmd.contains("P")) {
                char x = cmd.charAt(2);
                stack.push(x);
            }            
        }
 
        
        while(!stack.empty()) {
            stack_R.push(stack.pop());
        }
 
        StringBuilder sb = new StringBuilder();
        while(!stack_R.empty()) {
            sb.append(stack_R.pop());
        }
        System.out.println(sb);
    }
 
}