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

문제링크 : https://www.acmicpc.net/problem/1406

1406번: 에디터

 

풀이과정 : 처음에 하나의 스택안에 입력문자들을 받고, 커서를 가르키는 인덱스를 추적하면서,

상황에 따라 포문을 돌려가며 문제를 풀어서 비교적 간단하게 문제를 풀었는데.. 역시 시간초과가 떴다...!

#시간초과
import sys
lst = list(sys.stdin.readline().split())
cur_idx = len(lst)
testcase = int(input())

for _ in range(testcase):
    command = list(map(str, input().split()))
    if command[0] == "L":
        if cur_idx == 0:
            continue
        cur_idx -= 1
    elif command[0] == "D":
        if cur_idx == len(lst):
            continue
        cur_idx += 1
    elif command[0] == "B":
        if cur_idx == 0:
            continue
        for i in range(cur_idx-1,len(lst)-1):
            lst[i] = lst[i+1]
        lst.pop()
        cur_idx -= 1
    elif command[0] == "P":
        lst.insert(cur_idx, command[1])
        cur_idx += 1

for _ in range(len(lst)):
    print(lst[_], end="")

 

특히 command가 "B" 일때 시간복잡도가 O(n)이라 어떻게 보면 당연한 결과겠다 싶었다.

결국 다른사람들의 풀이를 참고했고, 핵심은 두개의 스택을 만드는것이었다...!

lst1, lst2를 각각의 스택이라 생각하고 문자들을 lst1 -> lst2  또는 lst2 -> lst1으로 넘겨받으면서

그 넘겨받는 중간위치가 커서의 위치라 생각하면 된다.

그러면 append와 pop 만으로, 즉 O(1) 만으로 연산이 가능해지고 시간초과 없이 해결할 수 있다

 

 

답:

import sys
lst1 = list(sys.stdin.readline().rstrip())
lst2 = []
testcase = int(input())
for _ in range(testcase):
    command = list(sys.stdin.readline().split())
    if command[0] == "L":
        if lst1:
            lst2.append(lst1.pop())
    elif command[0] == "D":
        if lst2:
            lst1.append(lst2.pop())
    elif command[0] == "B":
        if lst1:
            lst1.pop()
    elif command[0] == "P":
        lst1.append(command[1])

lst1.extend(reversed(lst2))
print(''.join(lst1))

 

후기 : 스택 두개에 담을 생각을 어떻게 했을까... 아직 자료구조에 대한 이해가 부족한것 같다.