[백준] 1406 파이썬(python) : 에디터 - 이중stack

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

1406번: 에디터

 

 

 

시간이 오래걸리는 insert대신 append를 del 대신 pop을 사용하면 O(1)로 문제를 해결할 수 있다.

 

왼쪽으로 커서 이동은 top에 있는 원소를 다른 스택에 옮기고, 오른쪽으로 커서 이동은 다른 스택의 top에서 원래 스택으로 옮기는 방식이다.

 

import sys
string = list(sys.stdin.readline().rstrip()) #1
string2 = [] #2
n = int(sys.stdin.readline())
for _ in range(n):
    command = sys.stdin.readline().rstrip()
    if command[0] == 'P': #3
        string.append(command[2])
    elif command[0] == 'L' and string != []: #4
        string2.append(string.pop())
    elif command[0] == 'D' and string2 != []: #5
        string.append(string2.pop())
    elif command[0] == 'B' and string != []: #6
        string.pop()
print(''.join(string)+ ''.join(reversed(string2))) #7

 

#1 : 입력값을 받은 스택

#2 : 값을 옮겨 받을 스택

#3 : 명령이 P이면 원래 스택에 값 추가

#4 : 명령이 L이고 원래 스택이 비어있지 않으면 원래 스택 top원소를 빼서 다른 스택에 삽입

#5 : 명령이 D이고 다른 스택이 비어있지 않으면 다른 스택 top원소를 빼서 원래 스택에 삽입

#6 : 명령이 B이고 원래 스택이 비어있지 않으면 원래 스택 top원소를 빼서 삭제

#7 : 다른 스택은 원래 스택 기준에서 순서가 반대이므로 reversed함수를 사용해서 문자열 합쳐서 출력해 준다.

 

스택 문제에서 스택을 2개로 나눠서 해결하는 방법이 기발한것 같다. 시간복잡도도 O(1)로 엄청나게 낮출 수 있다. 스택 문제 연습을 열심히 하려는 마음이 든다.

 

https://hgk5722.tistory.com/229

[백준] 17413 파이썬(python) : 단어 뒤집기 2