[PS] BOJ1046 에디터 ( 자료구조 ) with Python,JAVA

 

◎ 문제

1406번: 에디터

 

◎ 문제풀이

 

자료구조의 힘을 알 수 있는 문제이다. 적절한 자료구조는 시간복잡도를 현격히 줄일 수 있다. 내가 처음 구현했던 코드는 시간초과가 발생했다. 

 

처음 구현한 코드

import sys
input = sys.stdin.readline

data = list(input().strip("\n"))
cursor = len(data)
n = int(input())

def editor(data,op) : 
    global cursor
    if op[0] == "P" :
      data.insert(cursor,op[1]) #O(N) 시간초과발생
      cursor += 1
      
    elif op[0] =="L" :
      if cursor != 0 : cursor -= 1
      
    elif op[0] == "D" :
      if cursor != len(data) : cursor += 1
        
    elif op[0] == "B" :
      if cursor != 0 :
        del data[cursor-1] #O(N) 시간초과발생
        cursor -= 1

for _ in range(n) :
  op = input().split()
  editor(data,op)

for value in data :
  print(value,end="")

 

파이썬이 제공하는 insert 메소드와 del 함수를 썼는데, 시간복잡도가 O(N)이다. 연산의 개수가 최대 50만개이다. 문자열의 길이는 최대 10만개이다. O(N)이 시간복잡도라면 10만의 시간복잡도를 50만번 반복하게 된다. 시간제한이 0.3초인 문제이므로 위 코드는 정답이 아니다. 

 

STACK 두 개를 활용하여 위 문제를 풀어보자. 

 

 

 

 

STACK 2개를 만들고 STACK1에 입력받은 문자를 하나씩 넣어주었다. 이 문제는 커서(CURSOR)가 중요하다. 

 

자료구조가 하나만 있을 때, 커서는 포인터가 된다.

자료구조가 두개가 있을 때, 커서는 경계가 된다. 

 

커서를 기준으로 좌측은 STACK1에, 우측은 STACK2에 넣는다. 에디터의 커서를 왼쪽으로 이동해보자.

 

 

한번더 왼쪽으로 이동해보자.

 

 

이번에는 오른쪽으로 이동해보자.

 

 

 

하나의 자료구조만 있으면 커서는 '포인터'가 된다. INSERT, DELETE를 하려면 포인터로 '탐색'해야한다. 시간복잡도는 O(N)이다. 자료구조가 두개로 나뉘면 두 개의 자료구조의 끝은 CURSOR가 된다. 그러면 INSERT와 DELETE가 간단히 PUSH와 POP으로 구현된다. 시간복잡도는 O(1)이 된다. 경계를 중심으로 자료구조 수정이 필요할 때, 자료구조를 하나가 아닌 두개로 분리하면 문제를 빠르고 쉽게 해결할 수 있다.

 

STACK을 활용한 코드 

 

Python

import sys
input = sys.stdin.readline


stack1= list(input().rstrip())
stack2 = []

n = int(input())

for _ in range(n) :
  op = input().split()
  if op[0] == "P" : stack1.append(op[1])
  elif op[0] == "L" : 
    if stack1 : stack2.append(stack1.pop())
  elif op[0] == "D" : 
    if stack2 : stack1.append(stack2.pop())
  elif op[0] == "B" : 
    if stack1 : stack1.pop()

while stack2 :
  stack1.append(stack2.pop())

for value in stack1 :
  print(value,end="")

 

JAVA

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.stream.IntStream;

//BOJ1406 에디터 STACK
public class Stack2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Stack<Character> stack1 = new Stack<>();
        Stack<Character> stack2 = new Stack<>();

        IntStream str = br.readLine().chars(); 
        str.forEach( ch -> stack1.push((char)ch));

        int n = Integer.parseInt(br.readLine());

        while (n-- > 0) {
            String[] op = br.readLine().split(" ");

            if(op[0].equals("L")){
                if(!stack1.empty()) stack2.push(stack1.pop());
            }else if(op[0].equals("D")){
                if(!stack2.empty()) stack1.push(stack2.pop());
            }else if (op[0].equals("B")){
                if(!stack1.empty()) stack1.pop();
            }else {
                stack1.push(op[1].charAt(0));
            }
        }

        while(!stack2.empty()) {
            stack1.push(stack2.pop());
        }
        stack1.forEach(sb::append); 
        System.out.println(sb);
    }
}