[ 파이썬(python) ] 백준 1406 - 에디터

📌 백준 1406 - 에디터

문제 설명

---

💡 나의 풀이

어제 응시했던 2021 카카오 인턴십 온라인 코딩 테스트에서도 비슷한 문제가 나왔다. 다만 거기서는 ctl + z기능도 포함되어있어서 조금 더 어려웠던것 같다. 나중에 해설이 나오면 어떤 방식으로 접근했는지 살펴봐야겠다.

 

이 문제는 어떻게 풀어야 할지 정말 많이 고민했는데,  결과적으로 stack 혹은 deque를 사용하면 쉽게 풀 수 있는 문제였다. 그리고 문제에서 시간 제한이 0.3초로 주어져있어서 O(N^2)으로는 풀 수 없다.

 

첫 시도에서 len(s)만큼 cursor를 선언해서 풀었지만 B 명령어의 예외처리를 어떻게 해줘야할지 모르겠다. 그리고 cursor를 사용해서 insert와 remove를 사용했는데 각각 시간복잡도가 O(N)이고 입력인 명령어를 받기위해 처음에 반복문을 한번 선언했기 때문에 이중 반복문이 되는 형태였다.

 

처음에 deque로 풀고, 두번째는 stack으로 풀었다. 두 방식 모두 시간 복잡도가 O(N)이기 때문에 실행시간은 각각 364ms, 352ms로 차이가 많지 않았다.

 

1. 빈 deque 혹은 stack을 선언한다.
2. L: 커서를 왼쪽으로 한 칸 옮기는 명령어인 L이 들어오면 L보다 오른쪽에 있는 값들 모두 deque_R로 옮긴다. 옮길때는 append가 아닌 appendleft()로 해주는것을 잊지 말자.
3. D: 반대로 커서가 오른쪽으로 한 칸 옮기는 명령어인 D가 들어오면 D보다 왼쪽에 있는 값들 모두 deque_L로 옮긴다. 옮길 때는 append가 아닌 appendleft()로 해주는것을 잊지 말자.
4. B: 삭제하는 기능은 pop으로 해결한다.
5. P: 추가하는 기능은 append로 해결한다.

 

명령어 L, D, B 공통적으로 커서가 문장의 맨 앞 / 맨 뒤면 무시하라는 조건이 있는데, 이는 deque의 길이보다 작으면 무시하는 조건을 넣어주면 된다.
deque의 출력은 리스트를 서로 더해주고 join을 해주면 되는데, stack같은 경우는 거꾸로 뒤집어줘야(reversed) 정상적인 출력이 나온다.

# deque
import sys
from collections import deque
input = sys.stdin.readline

deque_L, deque_R = list(input().strip()), deque([])
m = int(input())

for i in range(m):
    command = input().split()
    if 'L' in command:
        if not deque_L:
            continue
        deque_R.appendleft(deque_L.pop())

    elif 'D' in command:
        if not deque_R:
            continue
        deque_L.append(deque_R.popleft())

    elif 'B' in command:
        if not deque_L:
            continue
        deque_L.pop()

    else:
        deque_L.append(command[1])

print(''.join(deque_L + list(deque_R)))

# stack
import sys
input = sys.stdin.readline

stack_L, stack_R = list(input().strip()), []
m = int(input())

for i in range(m):
    command = input().split()
    if 'L' in command:
        if not stack_L:
            continue
        stack_R.append(stack_L.pop())

    elif 'D' in command:
        if not stack_R:
            continue
        stack_L.append(stack_R.pop())

    elif 'B' in command:
        if not stack_L:
            continue
        stack_L.pop()

    else:
        stack_L.append(command[1])

print(''.join(stack_L + list(reversed(stack_R))))