[백준 파이썬] #1406. 에디터

풀기 전 생각해보기😮

• 시간초과가 발생한다면 자료구조를 사용해보기
• 2개의 스택 구조를 사용해보자

 

---

풀이🛫

# pypy3 채점으로 정답

# 스택을 하나 더 사용하는 방식을 사용

left = list(input())
right = []           # 임시 스택 공간
N = len(left)
M = int(input())
for m in range(M):
    ord = list(input().split())

    if ord[0] == 'L':               # 커서 왼쪽 이동
        if left:                         # inp이 존재할 때
            right.append(left.pop())      # right 공간에 저장
    elif ord[0] == 'D':             # 커서 오른쪽 이동
        if right:                        # temp가 존재할 때
            left.append(right.pop())      # temp에서 가져와 다시 저장
    elif ord[0] == 'B':             # 커서 왼쪽 문자 삭제
        if left:
            left.pop()
    else:                           # ord[1] 문자 추가
        left.append(ord[1])

# 모든 ord가 종료되면 temp에 저장된 문자를 가져와 다시 저장
left.extend(reversed(right))
print(''.join(left))

 

핵심 정리🎁

• 구글링을 해보면 deque를 이용해 풀이하시는 분도 계셨다
• 일반적으로는 위와 같이, 스택을 2개 사용하는 방식을 이용한 풀이가 좋은 풀이로 보였다
• 특정 인덱스에서 요소를 제거할 때 매우 주의해야 한다. 특정 위치에서 요소를 제거하면 그 이후의 요소들이 다시 배치되어야 하기 때문에 시간복잡도가 매우 증가하게 된다
• 왼쪽(left), 오른쪽(right)에 두 개의 스택이 있다고 생각하고, 커서의 위치에 따라 요소가 오가는 상황을 생각해볼 수 있었다. 마치 자석이 서로 붙었다 떼어지는 듯한 모습을 상상해볼 수 있다.

링크💎

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

1406번: 에디터