꾸준히 개발하기

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

처음에 보고 단순 구현 문제라고 생각했다. 물론 그렇게 단순하게 생각해서 문자열 슬라이싱했다가 처참하게 시간초과가 났다. 당연하긴 하다. B나 P 입력이 들어오면 문자열 cursor번째까지 살펴보고, 또 그 뒤도 살펴보는 식으로 문자열의 길이만큼을 계속 살펴보게 되어 시간효율성이 떨어진다. 

따라서 커서가 움직일 때마다 해당 데이터를 뽑아서 갖고 있는 리스트(pop_data)를 추가하는 방향으로 코드를 수정했다. 커서를 기준으로 왼쪽 데이터가 data 리스트에, 오른쪽 데이터가 pop_data에 저장되는 식이다! 그러면 매번 O(1)의 시간복잡도만 발생하여 최대 명령어의 개수(M)까지만 시간이 소요되어 0.3초라는 시간제한을 통과할 수 있다.

• L : 커서 왼쪽 이동. data의 길이가 0이 아닐 때, data.pop() -> pop_data에 append()
• D : 커서 오른쪽 이동. pop_data의 길이가 0이 아닐 때, pop_data.pop() -> data에 append()
• B : 커서 기준 왼쪽의 글자 제거. data의 길이가 0이 아닐 때, data.pop()
• P $ : 커서 기준 왼쪽에 글자 삽입. data에 바로 글자 append()

리스트를 커서를 기준으로 2개 둔다는 아이디어만 떠올리면 금방 구현할 수 있는 문제다. 마지막에 출력해줄 때는 data안의 요소와 pop_data안의 요소는 역순으로 출력해주면 된다. (리스트의 역순 접근은 [::-1] 이다. 잊지말자!)

코드는 다음과 같다.

import sys

input = sys.stdin.readline

data = list(map(str, input().replace("\n", "")))
m = int(input())
commands = [input() for _ in range(m)]

pop_data = []
for c in commands:
    if c[0] == "L":
        if len(data) != 0:
            pop_data.append(data.pop())
        else:
            continue
    elif c[0] == "D":
        if len(pop_data) != 0:
            data.append(pop_data.pop())
        else:
            continue
    elif c[0] == "B":
        if len(data) != 0:
            data.pop()
        else:
            continue
    elif c[0] == "P":
        input_c = list(c.split(" "))[1][0]
        data.append(input_c)


print("".join(map(str, data)) + "".join(map(str, pop_data[::-1])))

스택을 언제 쓰는게 효율적인지 살짝씩 감을 잡아가는 것 같다. 더 풀어보자!