(python) 1406 에디터 스택 풀이

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

1406번: 에디터

 

연결리스트 공부 중 1406번 에디터 문제를 보았지만 연결리스트로 풀기가 상당히 힘들어 스택으로 풀었다.

 

---

풀이

커서라는 것을 코딩으로 구현을 해야 하는데 연결리스트로는 양뱡향 원형 리스트로도 풀 수는 있지만 

클래스 정의에 노드 정의까지 연결리스트 공부는 정말 잘됐지만 풀기에 너무 오래 걸려서 포기했다.

 

커서 이동에서 스택 두 개를 이용하면 정말 간단하게 풀 수 있다.

커서를 이동할 때마다 스택 요소를 다른 스택으로 이동시켜 주면 해결이다.

 

처음 문자열을 받아올 때 리스트로 받아오면서 스택에 넣어주면 따로따로 들어가게 된다.

 

stack_a = list(sys.stdin.readline().rstrip())

.rstrip() 은 문자열 끝의 \n 을 날려준다.

 

이제 편집기 명령어 입력을 받을 건데 입력 또한 반복문 안에서 리스트로 받아 변수에 저장해 준다.

L 문자가 들어오면 커서를 왼쪽으로 이동시킨다.

스택 a 요소가 비어있지 않다면 pop을 이용하여 빼주면서 스택 b로 넣어준다.

# pop은 스택 맨 뒤 요소를 반환 후 빼준다.

 

D 문자도 L문자의 반대로스택 b 요소가 비어있지 않다면 pop을 이용하여 빼주면서 스택 a로 넣어준다.

넣을 때는 append를 이용하면 스택 뒤로 이동된다.

 

B 문자는 커서 왼쪽 요소를 삭제시키는데 커서는 항상 스택 a의 끝에 있다고 생각하면 된다.

스택 a가 비어있지 않다면 pop을 이용해서 스택 a의 마지막 요소만 빼준다.

 

마지막 P는 문자를 추가하는 것이다.

이때 위에서 편집기 명령어를 리스트로 받은 이유이다. 

P $

여기서 리스트 요소로 보면 P는 리스트 인덱스 0번

$ 문자는 리스트 인덱스 2번이다.

커서 왼쪽에 추가하는 것이기에 append로 스택 a에 넣어준다.

 

마지막 출력은 스택  b에 있던 문자도 출력하기 때문에 여러 방법이 있겠지만

필자는 b리스트를 reversed로 뒤집어 스택 a에 넣어주었다.

반복문으로 스택 b를 pop을 해서 스택 a에 append 해도 되겠다.

 

---

 완성 코드

sys를 사용하지 않으면 시간초과가 발생한다.

import sys

stack_a = list(sys.stdin.readline().rstrip())
stack_b = []
num = int(input())

for _ in range(num):
    p = list(sys.stdin.readline())
    if p[0] == "L":
        if len(stack_a) != 0:
            stack_b.append(stack_a.pop())
    elif p[0] == "D":
        if len(stack_b) != 0:
            stack_a.append(stack_b.pop())
    elif p[0] == "B":
        if len(stack_a) != 0:
            stack_a.pop()
    else:
        stack_a.append(p[2])
        
stack_b = list(reversed(stack_b))
result = stack_a + stack_b

print(*result, sep="")