백준 1406 에디터

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

1406번: 에디터

스택에 대해 새롭게 접근할 수 있는 재밌는 문제라 다시 정리를 해보려고 한다.

 

문제를 처음 접근했을땐 단순 구현문제로 접근하여 아래와 같이 코딩을 하였으나 

시간 초과가 되어버렸다.

data = list(map(str,input()))
n = int(input())
cursor = len(data)

for _ in range(n):
    x = input().split()

    if x[0] == 'L' and cursor != 0:
        cursor -= 1

    elif x[0] == 'D' and cursor != len(data):
        cursor += 1

    elif x[0] == 'B' and cursor != 0:
            del data[cursor-1]
            cursor -= 1

    elif x[0] == 'P':
        data.insert(cursor,x[1])
        cursor += 1

print(''.join(data))

 

시간 복잡도를 계산해봤는데 list에 insert(), del가 O(n)이라는 사실을 알고 O(1)인 append(), pop()으로 바꾸기로 하였다.

 

커서를 왼쪽으로 옮긴다는 의미는 삭제가 아니라 잠시 기억해놨다가 다시 꺼낼수있다는 의미이고

오른쪽으로 옮긴다는 의미도 잠시 기억해놨다가 언제든 다시 꺼낼수있다는 의미이다.

즉, stack 2개를 이용해서 풀어 나갈 수 있다는 점이다!

 

import sys

stack1 = list(sys.stdin.readline().strip())
stack2 = []
n = int(sys.stdin.readline())
cursor = len(stack1)

for _ in range(n):
    x = sys.stdin.readline().split()

    if x[0] == 'L' and stack1 != []:
        stack2.append(stack1.pop())

    elif x[0] == 'D' and stack2 != []:
        stack1.append(stack2.pop())

    elif x[0] == 'B' and stack1 != []:
        stack1.pop()

    elif x[0] == 'P':
        stack1.append(x[1])

print(''.join(stack1 + list(reversed(stack2))))

시간을 최대한 빠르게 하기위해 sys 라이브러리를 사용했으며 stack != []는 그 스택이 비어있으면 

 

append 및 pop이 안되기때문에 이를 방지해놓은 조건이다.