34 삐약 : 백준 1406[바킹독 문제 풀이|연결리스트|JAVA]

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

1406번: 에디터

 

 

 

---

 

 

1트 : 시간 초과 : Linked List 사용

 

package BKD_0x3_LinkedList;

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

public class BOJ_1406 {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        char[] input = bf.readLine().toCharArray();
        LinkedList<Character> characters = new LinkedList<>();

        for(char c : input) characters.add(c);

        int curser =characters.size();

        int N = Integer.parseInt(bf.readLine());

        for(int i=0;i<N;i++){
            char[] command = bf.readLine().toCharArray();
            switch (command[0]){
                case 'L':
                    if(curser!=0) curser--;
                    break;
                case 'D':
                    if(curser<characters.size()) curser++;
                    break;
                case 'B':
                    if(curser!=0){
                        characters.remove(curser-1);
                        curser--;
                    }
                    break;
                case 'P':
                    characters.add(curser,command[2]);
                    curser++;
                    break;
                default: break;
            }

        }

        String result="";
        for (char c:characters) {
            result+=c;
        }

        System.out.println(result);




    }


}

 

LinkedList 사용 시 시간 초과 이유

• 문제 자체에서 삽입/삭제를 빈번히 요구하는데 기존 Array보다 더 빠른 처리를 요구하고 있음.

==> 검색 시에 인덱스를 통해 접근 하는 것이 아니기 때문에 최악의 경우 모든 요소들을 다 살펴봐야 한다는 점. 

 

 

---

 

 

2트 : 해결 : Stack

 

❗❗ 핵심 ❗❗

- BufferedReader & BufferedWriter 적용 시간 단축
- 편집을 위한 문자열 탐색 시간 단축 필요
- 문제집 이름이 연결리스트라고 냅다 LinkedList를 써버리고자 하는 단순한 발상 극뽁
- Linked List를 사용했을 경우 ListIterator를 사용하여 양방향 탐색이 가능하도록 하여 시간 단축
- Stack을 사용하여 탐색 시간 단축

 

 

 

package BKD_0x3_LinkedList;

import java.io.*;
import java.util.LinkedList;
import java.util.Stack;

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

        Stack<Character> leftStack = new Stack<>();
        Stack<Character> rightStack = new Stack<>();

        char[] input = bf.readLine().toCharArray();

        for(char c : input) leftStack.push(c); // 초기화

        int N = Integer.parseInt(bf.readLine());

        for(int i=0;i<N;i++){
            String command = bf.readLine();
            switch (command.charAt(0)){
                case 'L':
                    if(!leftStack.isEmpty()){
                        char c = leftStack.pop();
                        rightStack.push(c);
                    }
                    break;

                case 'D':
                    if(!rightStack.isEmpty()){
                        char c = rightStack.pop();
                        leftStack.push(c);
                    }
                    break;
                case 'B':
                    if(!leftStack.isEmpty()){
                        leftStack.pop();
                    }
                    break;
                case 'P':
                    leftStack.push(command.charAt(2));
                    break;
                default: break;
            }

        }

        while(!leftStack.isEmpty()) rightStack.push(leftStack.pop());

        while(!rightStack.isEmpty()) bw.write(rightStack.pop());

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

 

 

 

 

 

 

 

 

 

참고 : https://minhamina.tistory.com/17