[Boj/백준] 1406 Python

문제출처: https://www.acmicpc.net/problem/1406

1406번: 에디터

 

 

1. 문제 접근 방식

시간제한이 엄격하기 때문에 원래 풀려던 방법으로 풀면 시간초과가 발생할 것 같았다.

백준 5397번처럼 스택을 두개 두고 커서 옮길때마다 양스택으로 이동시키는 방법으로 접근했다.

 

 

2. 내가 푼 코드

import sys

lstack = list(map(str,sys.stdin.readline().strip()))
rstack = []

case = int(sys.stdin.readline())


for i in range(case):
    edit = sys.stdin.readline().split()
    if edit[0] == 'P':
        lstack.append(edit[1])
    elif edit[0] == 'L':
        if lstack:
            rstack.append(lstack.pop())
    elif edit[0] == 'D':
        if rstack:
            lstack.append(rstack.pop())
    elif edit[0] == 'B':
        if lstack:
            lstack.pop()


rstack.reverse()
print(''.join(lstack+rstack))

 

3. 결과 및 느낀점

처음에 edit[0]이 L일때 append메소드대신에 insert메소드를 사용했는데

insert메소드는 시간복잡도가 O(N)이라 시간초과가 발생했다.

append메소드를 사용하고 reverse시키면서 해결했다.

시간제한이 엄격할때는 insert함수보단 append함수를 사용하고 reverse시키는 방식을 사용하자.

또 reversed 메소드는 반환할 때 list(reversed(rstack))과 같이 list형으로 형변환시켜줘야 한다(원래는 reversed 객체를 반환하므로).

시간제한이 엄격한 스택 문제에서는 두 개의 스택을 활용하자.