[백준] 1406 - 에디터 (Python)

문제

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

제출 코드

import sys

stackLeft = list(sys.stdin.readline().strip()) 
stackRight = []
case = int(sys.stdin.readline()) 

for i in range(case):
    line = sys.stdin.readline()

    if line[0] == 'L':
        if len(stackLeft) == 0: 
            continue
        else:
            stackRight.append(stackLeft.pop())

    elif line[0] == 'D':
        if len(stackRight) == 0: 
            continue
        else:
            stackLeft.append(stackRight.pop()) 

    elif line[0] == 'B':
        if len(stackLeft) == 0: 
            continue
        else:
            stackLeft.pop()

    elif line[0] == 'P':
        stackLeft.append(line[2])  

for i in (stackLeft + list(reversed(stackRight))):
    print(i, end='') 

결과

---

정리

설명

일단 스택의 LIFO 개념을 사용하기 위해 '커서 기준 왼쪽' , '커서 기준 오른쪽' 이렇게 스택을 두개 만들었다.

• L일때
  조건1) 커서를 왼쪽으로 한 칸 옮김: stackLeft에서 pop을 해서 stackRight에 append
  조건2) 커서가 문장의 맨 앞이면 무시됨: stackLeft의 길이가 0이면 문장의 맨 앞이라는 뜻이므로 stackLeft의 길이가 0인지 비교

• D일때
  조건1) 커서를 오른쪽으로 한 칸 옮김: stackRight에서 pop을 해서 stackLeft에 append
  조건2) 커서가 문장의 맨 뒤이면 무시됨: stackRight의 길이가 0이면 문장의 뒤라는 뜻이므로 stackRight의 길이가 0인지 비교

예제1 과정)

예제2 과정)

KEY POINT

예제1에서 마지막 명령어까지 수행하면 stackRight에 글자가 한 개만 있어서 'stackLeft + stackRight'으로 운이 좋게 결과값을 맞게 얻을 수 있다. 하지만 예제2에서는 'stackLeft + stackRight'으로 결과값을 내면 우리가 원하는 결과가 나오지 않는다. 그 이유는 스택의 특징이 LIFO(Last-In, First-Out)이기 때문이다.
밑에 표를 보면 이해가 쉬울 것이다. 커서를 기준으로 스택을 왼쪽과 오른쪽으로 나눈 것이고 stackLeft에서 pop을 해서 stackRight에 append 했다는 것을 계속 생각해야 한다.

따라서! 결과값을 내기 위해 stackLeft와 stackRight를 합칠때 'stackLeft + list(reversed(stackRight))'로 해야 한다!!

주석있는 코드

import sys

# 커서 기준으로 Left와 Right로 나눈다
stackLeft = list(sys.stdin.readline().strip()) # 초기 문자열을 Left에 넣어준다
stackRight = []

# 입력할 명령어의 개수
case = int(sys.stdin.readline())

for i in range(case):
    line = sys.stdin.readline()

    # L일때
    # 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
    if line[0] == 'L':
        if len(stackLeft) == 0: # stackLeft가 0이면 커서가 문장의 맨 앞이라는 뜻
            continue
        else:
            stackRight.append(stackLeft.pop()) # Left 마지막에 있는 문자를 right로 옮겨줌으로써 커서를 옮긴다

    # D일때
    # 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
    elif line[0] == 'D':
        if len(stackRight) == 0: # stackRight가 0이면 커서가 문장의 맨 뒤라는 뜻
            continue
        else:
            stackLeft.append(stackRight.pop()) # Right 마지막에 있는 문자를 Left로 옮겨줌으로써 커서를 옮긴다

    # B일때
    # 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
    elif line[0] == 'B':
        if len(stackLeft) == 0: # stackLeft가 0이면 커서가 문장의 맨 앞이라는 뜻
            continue
        else:
            stackLeft.pop() # 문자 삭제

    # P일때
    # 문자를 커서 왼쪽에 추가함
    elif line[0] == 'P':
        stackLeft.append(line[2])  # 추가해야 되는 문자 추가


for i in (stackLeft + list(reversed(stackRight))):
    print(i, end='') # 한줄에 출력하기 위해 end='' 를 해줌

느낀점

처음에는 커서의 위치를 나타내는 int형 변수를 만들어서 구현해보려고 했는데 명령어 'L' 때문에 커서를 왼쪽으로 옮긴 상태에서 명령어 'P'가 나왔을때 커서 뒤에 있는 문자들을 한칸씩 미루고 문자를 추가하는 부분에서 어떻게 효율적으로 할 수 있을지 대해 고민을 하다가 stack의 개념을 이용할 수 있다는 것을 깨달았다.