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

1406번: 에디터

처음에는 문제의 요구사항대로 그냥 구현만 해주면 된다고 생각했다. 즉, 커서라는 변수를 하나 선언하고 커서의 위치에 따라 L, D, B, P라는 명령어 각각을 올바르게 수행해주면 된다고 생각한 후 코드를 작성했다.

import sys
input = sys.stdin.readline

'''
L: 커서를 왼쪽으로 한 칸 옮긴다 / 커서가 맨 앞이면 무시한다.
D: 커서를 오른쪽으로 한 칸 옮긴다 / 커서가 문장의 맨 뒤면 무시한다.
B: 커서 왼쪽에 있는 문자를 삭제한다 / 커서가 문장의 맨 앞이면 무시된다.
P $: $ 문자를 왼쪽에 추가한다.
'''

target_string = list(input().rstrip())
n = int(input())

cursor = len(target_string)

for _ in range(n):
    operation = input().rstrip()
    if operation[0] == 'P':
        _, input_char = operation.split(' ')
        target_string.insert(cursor, input_char)
        cursor += 1
    elif operation == 'L' and cursor > 0:
        cursor -= 1
    elif operation == 'D' and cursor <= len(target_string):
        cursor += 1
    elif operation == 'B' and cursor > 0:
        target_string.pop(cursor-1)
        if cursor > 0:
            cursor -= 1
            
print(''.join(target_string))

하지만 해당 반식은 시간초과가 발생한다. 사실 pop 연산을 맨 끝에서 수행한다면 문제가 없지만, pop 연산을 위와 같이 중간에서 사용한다면 시간이 굉장히 오래걸린다. 왜냐하면 중간에 한 값을 빼고 나머지 값은 모두 앞으로 땡겨와야 하기 때문에 최악의 경우 O(n)만큼의 시간이 소요된다. 현재 총 500,000 명령어를 입력받을 수 있고, 문자열의 길이는 최대 100,000이므로 최악의 경우 50,000,000,000번 연산을 수행해야 한다. (물론 정확히 계산하면 더 적게 걸리지만, 그만큼 많이 소요된다.)

 

따라서 두 번째로 생각한 방법이 커서 변수를 사용해 중간에서 pop을 사용하지 말고, 커서를 기준으로 리스트를 두 개 사용하는 방식을 떠올렸다. 예를 들어, "abcd"라는 문자열이 주어지고 커서가 b오른쪽에 있는 상태면 한 쪽에는 "ab" 다른 쪽에는 "cd"를 놓는 것이다. (단, 커서를 기준으로 오른쪽은 반대로 저장할 것이다. 스택의 특성상 반대로 저장하는 것이 편하다. 즉, 위 경우 "cd"가 아니라 "dc"로 저장한다.) 해당 코드는 아래와 같다.

import sys
input = sys.stdin.readline

left_target_string = list(input().rstrip())
right_target_string = list()
n = int(input())

for _ in range(n):
    operation = input().rstrip()
    if operation[0] == 'P':
        _, input_char = operation.split(' ')
        left_target_string.append(input_char)
    elif operation == 'L' and left_target_string:
        right_target_string.append(left_target_string.pop())
    elif operation == 'D' and right_target_string:
        left_target_string.append(right_target_string.pop())
    elif operation == 'B' and left_target_string:
        left_target_string.pop()

left_target_string.extend(reversed(right_target_string))
print(''.join(left_target_string))