백준 1406 에디터 - 파이썬

 

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

1406번: 에디터

 

 

 

가장 잘 알려진 풀이는 스택을 두 개 사용하는 것이다.

 

 

커서를 기준으로 왼쪽에 위치한 스택과 오른쪽에 위치한 스택 두 개를 만든다.

오른쪽 스택은 방향을 뒤집어두었다. pop 하면 왼쪽에 있는 원소가 나오고, append도 왼쪽에 된다.

 

처음에는 문장의 맨 뒤에 커서가 위치하므로 왼쪽 스택에 문자를 순서대로 넣어두면 된다. 커서는 항상 left 리스트 오른쪽에 있다.

 

 

만약 "P"라는 명령어가 들어오면 "$" 원소를 커서 왼쪽에 추가해야 한다.

그냥 커서 왼쪽인 left 리스트에 append 해주면 된다.

 

 

"L"이라는 명령어가 들어오면 커서를 왼쪽으로 한 칸 옮겨야 한다.

하지만 커서를 직접 옮길 필요는 없다.

그냥 left 리스트에서 마지막 원소를 pop 해서 right 리스트에 append 해주면 커서를 옮긴 것과 같은 효과가 나타난다.

"L" 명령어를 두 번 연속 수행하면 아래와 같다. right 리스트가 뒤집혀 있다는 걸 잊지 말자.

 

 

반대로 "D" 명령어가 들어오면 right 리스트의 마지막 원소를 pop 해서 left 리스트에 append 해주면 된다.

 

 

 

"B" 명령어가 들어오면 커서 왼쪽의 문자를 삭제해야 한다.

그냥 left 리스트의 원소를 하나 pop 하면 된다.

 

 

 

모든 조작이 끝나면 문자열을 출력해야 한다. 

위의 그림과 같은 경우에는 최종 결과가 "ABDX"가 된다.

right 리스트는 뒤집혀있는 걸 고려해서 출력하면 답을 구할 수 있다.

 

 

 

코드로 작성할 때는 빈 리스트를 pop 하면 오류가 나니까 left나 right에 원소가 있는지를 꼭 확인해야 한다.

그리고 빠른 입출력을 안하면 시간 초과가 뜰 수도 있을 것 같다.

 

from sys import stdin

left = list(input())
right = []

for _ in range(int(input())):
    command = list(stdin.readline().split())
    if command[0] == 'L' and left:
        right.append(left.pop())
    elif command[0] == 'D' and right:
        left.append(right.pop())
    elif command[0] == 'B' and left:
        left.pop()
    elif command[0] == 'P':
        left.append(command[1])

answer = left + right[::-1]
print(''.join(answer))

 

 

---

 

 

사실 이 문제는 연결 리스트로도 풀 수 있다.

공부를 해보고 싶다면 직접 구현해볼 수는 있다.

참고로 내가 짠 더러운 코드는 스택 풀이보다 성능 면에서 4배 정도 느렸다.

 

 

from sys import stdin

# 연결리스트의 노드 클래스
class ListNode:
    def __init__(self, val, prev, next):
        self.val = val
        self.prev = prev
        self.next = next

# 연결리스트의 head
head = ListNode('dummy', None, None)
curr = head

init = input() # 초기 문자열
for i in range(len(init)): # 초기 문자열을 연결리스트로 만들어 둠
    new_node = ListNode(init[i], None, None)
    curr.next = new_node
    new_node.prev = curr
    curr = new_node

# 명령어들 처리
for _ in range(int(input())):
    command = stdin.readline().rstrip()
    if command == 'L':
        if curr.val != 'dummy':
            curr = curr.prev
    elif command == 'D':
        if curr.next:
            curr = curr.next
    elif command == 'B':
        if curr.val != 'dummy':
            curr = curr.prev
            if curr.next.next:
                curr.next = curr.next.next
                curr.next.prev = curr
            else:
                curr.next = None
    else:
        new_node = ListNode(command[-1], None, None)
        if curr.next:
            new_node.next = curr.next
            curr.next.prev = new_node
        curr.next = new_node
        new_node.prev = curr
        curr = new_node

# head 다음 노드부터 출력
print_node = head.next
while print_node:
    print(print_node.val, end='')
    print_node = print_node.next