[1406] 에디터 - stack, ArrayDeque (백준, Java)

 

처음에 다음과 같은 리스트로 구현을 했다.

 

▶️list 이용해 푼 코드

import java.util.*;
import java.io.*;
    
    public class Main {
        public static void main(String[] args) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String str = br.readLine();
            int M = Integer.parseInt(br.readLine());
    
            List<Character> list = new ArrayList<>();
    
            for (int i = 0; i < str.length(); i++) {
                list.add(str.charAt(i));
            }
            int cursor = list.size();
            StringTokenizer st;
            for (int i = 0; i < M; i++) {
                st  = new StringTokenizer(br.readLine());
    
                char cmd = st.nextToken().charAt(0);
    
                switch (cmd){
                    case 'L':
                        if (cursor > 0)
                            cursor--;
                        break;
                    case 'D':
                        if (cursor < list.size())
                            cursor++;
                        break;
                    case 'B':
                        if (cursor == 0) continue;
                        if (cursor == list.size()) {
                            cursor--;
                            list.remove(cursor);
                            break;
                        }
                        list.remove(cursor - 1);
                        cursor--;
                        break;
                    case 'P':
                        list.add(cursor, st.nextToken().charAt(0));
    
                        if (cursor <=  list.size()) cursor++;
                        break;
                }
            }
            for (int i = 0; i < list.size(); i++) {
                System.out.print(list.get(i));
            }
        }
    }

 

이같은 경우 L, D에서 커서 왼 오로 이동할 때는 cursor의 값만 변화시켜서 O(1) 시간이 들지만 B, P 같은 삭제, 삽입 동작의 경우에는 각각 O(N) 시간이 소요된다.

 

리스트는 특정 위치에 삽입을 할 때 삽입 후 나머지 요소들을 뒤로 밀고,

삭제할 때는 특정 요소를 지운 뒤 뒤쪽의 나머지 요소들을 땡긴다. 여기서 O(N)시간이 소요되는 것이다.

 

최악의 경우 처음 문자열 길이 N이 최대 100,000이고 입력 명령어 갯수 M이 최대 500,000개 들어와 삽입, 삭제 연산을 할 경우 O (N * M) = 5백억번의 연산을 하게된다. 그럼 당연히 시간 초과.

 

이 문제는 2개의 스택을 사용해서 각 연산에 O(1) 시간을 소요해야 풀 수 있는 문제였다. 커서의 인덱스를 계산하기 보다 스택에서 값들을 이동시켜가며 명령어 동작을 반영하면 된다.

 

초기 상태에서는 leftStack에 입력된 문자열을 다 담아놓고

 

L 연산 : lStack의 값을 하나 pop해 rStack에 push한다.

(lStack이 비어있지 않을 경우)

R연산 : rStack의 값을 하나 pop해 lStack에 push한다.

(rStack이 비어있지 않은 경우)

B연산 : lStack의 값을 pop

(lStack이 비어있지 않을 경우)

P연산 : lStack에 입력문자 push

를 구현해주면 된다 !

 

그리고 출력할 때는 왼쪽 스택의 모든 요소를 오른쪽에 옮기고

오른쪽 스택이 빌 때까지 출력해주면 된다.

그럼 최종 코드는 다음과 같다.

▶️Solution Code

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        String N = br.readLine();
        
        int M = Integer.parseInt(br.readLine());
        
        Deque<Character> lStack = new ArrayDeque<>();
        Deque<Character> rStack = new ArrayDeque<>();
        
        for (int i = 0; i < N.length(); i++) {
            lStack.push(N.charAt(i));
        }
        for (int i = 0; i < M; i++) {
            String str = br.readLine();
            
            char cmd = str.charAt(0);
            
            switch(cmd) {
                case 'L':
                    if (!lStack.isEmpty())
                        rStack.push(lStack.pop());
                    break;
                case 'D':
                    if (!rStack.isEmpty())
                        lStack.push(rStack.pop());
                    break;
                case 'B':
                    if (!lStack.isEmpty())
                        lStack.pop();
                    break;
                case 'P':
                    lStack.push(str.charAt(2));
                    break;
            }
        }
        while (!lStack.isEmpty()) {
            rStack.push(lStack.pop());
        }
        while (!rStack.isEmpty()) {
            sb.append(rStack.pop());
        }
        
        System.out.println(sb.toString());
        br.close();
    }
}

마지막으로 덧붙이자면 Stack 클래스에 들어가보면 다음과 같이 나와있는 걸 볼 수 있다.

 

→ 해석

Vector를 상속받아 벡터를 스택처럼 다룰 수 있도록 5가지 연산을 추가했다.

push와 pop, peek, empty, search 메서드를 제공한다.

스택이 처음 생성될 때 아무런 아이템도 들어있지 않다.

LIFO(Last In First Out) 스택 연산의 완전하고 일관된 기능은 Deque 인터페이스와 그 구현체들이 제공한다. 따라서 이 클래스보다 그것들을 우선 사용해라.

 

예를 들어

Deque<Integer> stack = new ArrayDeque<Integer>();

Stack은 모든 메소드에 synchronized 처리가 되어있어, 멀티 스레드 환경이 아닌 코테에서는 불필요한 성능 오버헤드가 발생한다고 한다.

ArrayDeque는 양쪽 끝에서 삽입과 삭제가 모두 가능한 배열로 스택이나 큐 처럼 사용할 수 있다.

Stack보다 빠르고 (동기화를 하지 않으니)

LinkedList보다 메모리를 적게 쓴다. (LinkedList는 데이터 하나 저장시마다 노드라는 객체를 만들어서 prev, next를 가리키는 포인터를 함께 가지고 다님)

 

따라서 Deque<Character> stack = new ArrayDeque<>(); 로 stack을 구현해주었다.

 

끝..