[백준 JAVA] 1406번 풀이 - 에디터 (LinkedList 와 Stack 💖중요!!)

 

문제 풀이 전

"연결 리스트" 가 힌트로 있길래 연결 리스트....? 오 "LinkedList"가 있구나! 

찾아본 뒤에 바로 뚱땅뚱땅 문제 풀이해서 제출했다. 

실버 2 난이도 문제인데 생각보다 쉽게 풀리기에 뭐지 싶었는데 아니나 다를까 "시간 초과"  오류가 떴다. 

이건 백퍼 LinkedList 문제인 것이 확실했다.... LinkedList 에 대해 좀더 찾아보니 

 

LinkedList 는 노드 끼리의 주소 포인터를 참조하는 구조라, ArrayList 와 다르게 중간에 데이터가 추가, 삭제 되어도 앞뒤로 땡길 필요가 없어 무한정 요소를 저장할 수 있는 장점이 있다고....

하지만 첫번째 , 마지막에 요소를 추가할 때는 O(1) 의 시간이 걸리지만, 중간 삽입은 삽입할 위치 탐색을 해야해서 O(n) 의 시간이 걸리는 자료 구조라고 한다. 

 

그래, 중간 삽입에서 O(n) 의 시간이 걸리면 안되는구나 . 확인

 

시간초과 났던 문제 풀이

package quiz;

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

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

        String s = br.readLine(); //abcd
        int idx = s.length(); //처음, 맨 뒤

        LinkedList<Character> list = new LinkedList<>();
        for(int i=0; i<s.length(); i++){
            list.add(s.charAt(i));
        }

        int cnt = Integer.parseInt(br.readLine()); //3
        StringTokenizer st;
        //명령 실행.
        for(int i=0; i < cnt; i++){
            st = new StringTokenizer(br.readLine(), " ");
            String order = st.nextToken();

            if(order.equals("L")){
                if(idx!=0){
                    idx--;
                }
            } else if(order.equals("D")){
                if(idx<list.size()){
                    idx++;
                }
            } else if(order.equals("B")){ //왼쪽꺼 삭제
                if(idx!=0){
                    if(idx==list.size()){
                        list.removeLast();
                        --idx;
                    } else {
                        list.remove(--idx);
                    }
                }
            } else if(order.equals("P")){ //문자를 커서에 추가
                char word = st.nextToken().charAt(0);
                if(idx==list.size()){
                    list.addLast(word);
                } else if(idx==0){
                    list.addFirst(word);
                } else {
                    list.add(idx,word);
                }
                ++idx;
                //list.add(idx++,word);
            }
        }

        StringBuilder sb = new StringBuilder();
        for(char a : list){
            sb.append(a);
        }
        System.out.println(sb);
    }
}

 

 

계속 되는 시간 초과 오류에 지쳐서.... 

구글링해보니 listIterator 를 활용해서 풀더라. 나는 그냥 Stack 으로 풀기로 했다. 

사실 이 문제를 처음 마주했을 때부터, AI 역량검사에서 봤던 물(?) 옮겨 담기 게임이 생각났다.

"이거 물 옮겨 담기 게임처럼 어디 TEMP 에 보관했다가 꺼냈다가 하면 안되나?" 라고 잠깐 생각했었다. 그런데 진짜 그렇게 풀면 되는거였다. 

 

leftStack 과 rightStack 을 만들어서 명령어에 따라 left 쪽 요소를 right 쪽에 옮기고 다시 담고... 삭제하고.... 추가하고.... 

이런 작업을 반복하면 되는거였다. ㅎㅎ.ㅎ...ㅎ 그래서 Stack 을 활용해 다시 풀게 된 방법 !!! 

아래 방법으로 풀었더니 한 번에 성공했다~~~~ 

 

성공한 문제 풀이 

package quiz;

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

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

        String s = br.readLine(); //abcd
        int idx = s.length(); //처음, 맨 뒤

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

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

        int cnt = Integer.parseInt(br.readLine()); //3
        StringTokenizer st;
        //명령 실행.
        for(int i=0; i < cnt; i++){
            st = new StringTokenizer(br.readLine(), " ");
            String order = st.nextToken();
            if(order.equals("L")){
                if(!leftStack.isEmpty()){
                    rightStack.push(leftStack.pop()); //꺼내서 오른쪽으로 둠
                }
            } else if(order.equals("D")){
                if(!rightStack.isEmpty()){
                    leftStack.push(rightStack.pop()); //꺼내서 왼쪽으로 다시.
                }
            } else if(order.equals("B")){ //왼쪽꺼 삭제
                if(!leftStack.isEmpty()){
                    leftStack.pop();
                }
            } else if(order.equals("P")){ //문자를 커서에 추가
                char word = st.nextToken().charAt(0);
                leftStack.push(word);
            }
        }

        StringBuilder sb = new StringBuilder();

        while(!leftStack.isEmpty()){
            rightStack.push(leftStack.pop());
        }
        while(!rightStack.isEmpty()){
            sb.append(rightStack.pop());
        }
        System.out.println(sb);

    }
}