백준 1406번: 에디터

문자열을 커서를 사용하여 커서 이동, 문자 삽입, 삭제를 한 후 결과를 출력하는 문제이다. L은 왼쪽으로 이동, D는 오른쪽으로 이동, B는 왼쪽 문자 제거, P x는 왼쪽에 x 삽입을 의미한다.

 

처음에는 단순하게 StringBuilder를 이용하여 작업을 수행하였다. 커서의 위치는 맨 앞은 0, 맨 뒤는 문자열의 길이로 구성하였다. 삽입은 맨 뒤는 append, 그 외에는 insert 후 cursor를 증가시켰고, 삭제는 현재 커서가 0 이상(앞에 문자가 있는 경우)에만 deleteCharAt을 수행 후, cursor를 감소시켰다. 단순 이동인 L, D는 각각의 맨 끝에서 더 가려고 하는게 아니라면 방향에 맞게 이동시켰다. 결과는 통과이나, 1초 정도 소요되었다.

StringBuilder sb = new StringBuilder(br.readLine());
int n = Integer.parseInt(br.readLine());
int cursor = sb.length();
for (int i = 0; i < n; i++) {
    String command = br.readLine();
    if (command.charAt(0) == 'P') {
        if (cursor == sb.length()) {
            sb.append(command.charAt(2));
        } else {
            sb.insert(cursor, command.charAt(2));
        }
        cursor++;
        //System.out.println(sb);
        continue;
    }
    if (command.charAt(0) == 'B') {
        if (cursor > 0) {
            sb.deleteCharAt(cursor - 1);
            cursor--;
        }
        //System.out.println(cursor + " " + sb);
        continue;
    }
    if (command.charAt(0) == 'L') {
        if (cursor == 0) {
            continue;
        }
        cursor--;
        continue;
    }
    if (cursor == sb.length()) {
        continue;
    }
    cursor++;
}

 

 

이러한 방법도 있지만, 두 개의 스택을 활용하여 문제를 해결하였다. 각각 커서의 왼쪽, 오른쪽에 위치한 문자들을 의미한다. 처음에는 문자들을 전부 왼쪽 스택에 push하였다. 이후, L 연산에 의해 왼쪽 스택에서 pop하여 오른쪽 스택으로 push해준다. D 연산은 오른쪽 스택에서 pop하여 왼쪽 스택에 push한다. 삭제는 커서 왼쪽을 하므로 왼쪽 스택에서 pop만 한다. P x는 왼쪽에 삽입하므로 왼쪽 스택에 push한다.

Deque<Character> left = new ArrayDeque<>();
Deque<Character> right = new ArrayDeque<>();

for (char c : initial.toCharArray()) {
    left.push(c);
}

for (int i = 0; i < m; i++) {
    String line = br.readLine();
    char cmd = line.charAt(0);
    
    switch (cmd) {
        case 'L':
            if (!left.isEmpty()) {
                right.push(left.pop());
            }
            break;
        case 'D':
            if (!right.isEmpty()) {
                left.push(right.pop());
            }
            break;
        case 'B':
            if (!left.isEmpty()) {
                left.pop();
            }
            break;
        case 'P':
            left.push(line.charAt(2));
            break;
    }
}

 

 

모든 명령어 완수 후, 각각의 스택의 문자열을 하나로 합친다. 왼쪽 스택은 커서 기준으로 왼쪽을 순서대로 push한 것이므로 reverse로 반전시켜야 하며, 오른쪽 스택은 오른쪽 순서대로 push이기 때문에 그대로 append한다.

StringBuilder sb = new StringBuilder();
for (char c : left) {
    sb.append(c);
}
sb.reverse();

for (char c : right) {
    sb.append(c);
}

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;

public class 에디터1406 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String initial = br.readLine();
        int m = Integer.parseInt(br.readLine().trim());
        
        Deque<Character> left = new ArrayDeque<>();
        Deque<Character> right = new ArrayDeque<>();
        
        for (char c : initial.toCharArray()) {
            left.push(c);
        }
        
        for (int i = 0; i < m; i++) {
            String line = br.readLine();
            char cmd = line.charAt(0);
            
            switch (cmd) {
                case 'L':
                    if (!left.isEmpty()) {
                        right.push(left.pop());
                    }
                    break;
                case 'D':
                    if (!right.isEmpty()) {
                        left.push(right.pop());
                    }
                    break;
                case 'B':
                    if (!left.isEmpty()) {
                        left.pop();
                    }
                    break;
                case 'P':
                    left.push(line.charAt(2));
                    break;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for (char c : left) {
            sb.append(c);
        }
        sb.reverse();
        
        for (char c : right) {
            sb.append(c);
        }
        
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
    }
}