1406번 에디터(java)

 

 이 문제를 접하면서 시간 제한에 신경을 더 쓰게 되었고, 조금이나마 시간을 줄이는 방법을 알 수 있었습니다. 저의 시행착오와 풀이를 한 번 살펴보도록 하겠습니다.

 

예제 이해

 

 문제를 접하면 sudo code를 약간이라도 적어보려고 노력하는데 처음 문제를 보며 든 생각은 if문이 많이 사용될 것 같다는 생각을 하고 일단 문제를 풀기만 하자라는 마음으로 풀이에 임했습니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str = br.readLine();
        int M = Integer.parseInt(br.readLine());
        int cursor = str.length();
        int strSize = str.length();

        String command = "";
        for (int i = 0; i < M; i++){
            command = br.readLine();
            if (cursor > strSize){
                continue;
            }else {
                if (command.equals("L")){
                    if (cursor > 0){
                        cursor--;
                    }
                }else if (command.equals("D")){
                    if (cursor < strSize){
                        cursor++;
                    }
                } else if (command.equals("B")){
                    if (cursor < 0){
                        continue;
                    }else if (cursor == 0){
                        str.substring(1, str.length());
                    }else {
                        str = str.substring(0, cursor - 1) + str.substring(cursor, strSize);
                    }
                    if (cursor > 0){
                        cursor--;
                    }
                    if (strSize > 0){
                        strSize--;
                    }
                } else if (command.split(" ")[0].equals("P")){
                    if (cursor == 0){
                        str = command.split(" ")[1] + str;
                    } else if (cursor == strSize) {
                        str = str + command.split(" ")[1];
                    }else {
                        str = str.substring(0, cursor) + command.split(" ")[1] + str.substring(cursor, strSize);
                    }
                    strSize++;
                    cursor++;
                }
            }
        }

        System.out.println(str);

        br.close();
    }
}

 

 처음 이렇게 난잡하게 코드를 짜고 제출을 하니 아래처럼 2%에서 시간 초과가 출력되었습니다...

 

 이후 출력문과 String으로 풀이를 하려다 보니 무거워져 시간 초과가 발생한다고 판단했고, Stack을 이용해서 풀이를 하였습니다. 그 결과는 55% 시간 초과... (아마 Stack으로도 풀이가 가능할 것 같습니다. 다 푼 후 다른 분들 풀이 참고함)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuffer sb = new StringBuffer();

        String str = br.readLine();
        Stack<Character> s = new Stack<>();
        for (int i = 0; i < str.length(); i++){
            s.push(str.charAt(i));
        }

        int cursor = str.length();
        int M = Integer.parseInt(br.readLine());

        for (int i = 0; i < M; i++){
            String commend = br.readLine();

            if (cursor < 0){
                cursor = 0;
            } else if (cursor >= s.size() + 1){
                cursor = s.size() + 1;
            }

            if (commend.equals("L")){
                if (cursor > 0){
                    cursor--;
                }
            } else if (commend.equals("D")){
                if (cursor < s.size()){
                    cursor++;
                }
            } else if (commend.equals("B")){
                if (cursor < 0){
                    cursor = 0;
                }else {
                    if (cursor == 0){
                        cursor--;
                    }else {
                        // 여기가 시간을 많이 잡아먹는다.(remove())
                        s.remove(cursor - 1);
                        cursor--;
                    }
                }
            } else{
                Character commendS = commend.charAt(2);
                s.add(cursor, commendS);
                cursor++;
            }
        }

        while (!s.empty()){
            sb.append(s.pop());
        }

        bw.write(String.valueOf(sb.reverse()));

        br.close();
        bw.flush();
        bw.close();
    }
}

 

구현 코드

 

 위에 실패들로 LinkedList와 ListIterator를 사용하여 풀기로 했습니다. 이유는 ListIterator가 커서의 역할을 할 수 있기 때문입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String str = br.readLine();
        int M = Integer.parseInt(br.readLine());
        LinkedList<Character> list = new LinkedList();

        for (int i = 0; i < str.length(); i++){
            list.add(str.charAt(i));
        }

        ListIterator<Character> listIterator = list.listIterator();
		
        // 커서 이동.
        while (listIterator.hasNext()){
            listIterator.next();
        }

        for (int i = 0; i < M; i++){
            String commend = br.readLine();
            if (commend.equals("L")){
                if (listIterator.hasPrevious()){
                    listIterator.previous();
                }
            }else if (commend.equals("D")) {
                if (listIterator.hasNext()){
                    listIterator.next();
                }
            }else if (commend.equals("B")) {
                if (listIterator.hasPrevious()){
                    listIterator.previous();
                    listIterator.remove();
                }
            }else {
                listIterator.add(commend.charAt(2));
            }
        }

        for (Character c : list) {
            bw.write(c);
        }

        br.close();
        bw.flush();
        bw.close();
    }
}

 

코드 설명

 

 ListIterator를 활용하여 커서처럼 이동 시키고 BufferdReader, BufferedWriter를 통해 입출력 성능을 끌어 올려 코드를 작성했습니다.