백준 1406번: 에디터

문제

---

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

1406번: 에디터

 

풀이

---

입력되는 메서드에 따라, 커서 위치에 정해진 기능을 수행하면 되는 문제라고 보면된다.

 

커서를 기준으로 삭제, 삽입 기능이 있길래 링크드 리스트를 떠올려 문제를 풀어나갔다.

 

삭제, 삽입을 배열로 풀면 삭제와 삽입 때마다 나머지 배열의 원소들이 앞,뒤로 움직이므로 최악의 경우 연산 하나의 시간복잡도는 O(M)이 된다.

 

M은 최대 60만 까지 될 수 있기 때문에, 배열로는 많은 시간을 잡아 먹을것으로 보였다.

 

먼저 입력값을 받고 링크드 리스트에 넣고 커서를 맨 뒤로 보내어 시작한다. 이후 M번의 메서드를 수행하면 된다.

 

각 메서드는 특정 기능을 하는데, L, D는 각각 커서를 앞 뒤로 옮기는것. B는 커서에 있는 요소를 지우는것.

그리고 P $, 커서 왼쪽에 P 다음에 오는 값을 추가하면 된다.

 

이렇게 링크드 리스트의 커서를 옮겨가며 기능을 수행하면 되는 문제였다.

---

이 문제를 다르게 푸는 방법도 있어 그 방법이 재밌어 보여 포스팅 하게 됐다.

 

방법은 링크드 리스트를 사용하는거 대신 스택을 이용하는것이다.

 

문제를 잘 생각하면 커서를 기준으로 양쪽에 스택을 두어 해결할 수 있다.

 

아래와 같이 문자열이 있을 때

abc | def

왼쪽 스택에 abc, 오른쪽 스택에 def가 있는것으로 볼 수 있다.

 

키 아이디어는 커서를 ab | cdef 처럼 왼쪽으로, 오른쪽으로 옮길 때 마다 왼쪽스택에서 pop하고 오른쪽 스택에 push 한다면 (오른쪽으로 옮길땐 반대로)커서를 옮긴것처럼 보일수 있다는 것이다.

 

또한 삭제는 왼쪽 스택에서 pop하고 삽입은 왼쪽 스택에 push하면 되는것이다.

 

---

 

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 s = br.readLine();
        Stack<Character> left = new Stack<Character>();
        Stack<Character> right = new Stack<Character>();
        for (int i=0; i<s.length(); i++) {
            left.push(s.charAt(i));
        }
        int m = Integer.parseInt(br.readLine());
        while (m-- > 0) {
            String[] line = br.readLine().split(" ");
            char what = line[0].charAt(0);
            if (what == 'L') {
                if (!left.empty()) {
                    right.push(left.pop());
                }
            } else if (what == 'D') {
                if (!right.empty()) {
                    left.push(right.pop());
                }
            } else if (what == 'P') {
                char c = line[1].charAt(0);
                left.push(c);
            } else if (what == 'B') {
                if (!left.empty()) {
                    left.pop();
                }
            }
        }
        while (!left.empty()) {
            right.push(left.pop());
        }
        StringBuilder sb = new StringBuilder();
        while (!right.empty()) {
            sb.append(right.pop());
        }
        System.out.println(sb);
    }
}

 

문제를 다른 시각에서 보는것이 문제해결능력을 기르는데 큰 도움이 될거같다는 생각이 드는 문제 풀이였다.