백준 1406번 에디터 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 1406 에디터

1406 에디터

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

1406번: 에디터

이번 문제는 (자료 구조, 스택, 연결 리스트) 알고리즘 문제로 문제의 내용은 단순히 편집기의 역할을 구현하는 것이었으나 커서를 이동하고 새로운 자료들을 추가하는 방법에 대해 찾기 위해 다른 분들의 코드를 참조했다.

---

코드

import sys
input = sys.stdin.readline

st1 = list(input().strip()) # \n 빼고 받기
st2 = [] # 뒤로 스택
n = int(input())

for i in range(n):
    C = input().split() # 리스트로 받아주기
    if C[0] == 'L' and st1: # st1에 값이 있다면 하나빼고 스택 2에 추가
        st2.append(st1.pop())
    elif C[0] == 'D' and st2: # st2에 값이 있다면 하나빼고 스택 1에 추가
        st1.append(st2.pop())
    elif C[0] == 'B' and st1: # st1에 값이 있다면 하나 지움
        st1.pop()
    elif C[0] == 'P': # P면 커서뒤에 C[1] 추가
        st1.append(C[1])

st1.extend(reversed(st2)) # 스택2는 뒤집어서 합쳐줌
print(''.join(st1))

---

풀이

시간초과 없이 빠른 풀이를 위해서는 스택을 이용한 방법을 이용하면 된다. 이 방법을 연결 리스트라고 칭하는 것 같다.

그 방법

위 그림과 같이 두 개의 스택을 선언해주고 커서를 왼쪽으로 이동할 때는 한 글자씩 st1에서 빼고 st2에 추가한다. 반대의 경우와 새로운 글을 삽입하는 경우에 대해 코드를 작성하여 준다. 스택의 개념으로는 두 리스트를 합칠 때 st2를 거꾸로 뒤집어 이어주면 답이 완성된다. 처음 이 방법을 접하고 아직 내가 멀었다는 것과 자료 구조를 다루는 것에 흥미를 느끼게 되었다. 거기다 연산 시간도 빠르니 정말 좋은 방법 같다. 자세한 풀이는 코드에 주석처리로 작성하였다.

---

풀이 결과

1406 풀이 결과