[백준/파이썬] 1406번: 에디터

본문과는 상관없는 이미지(출처:google)

이번 문제는 간단해보이면서도 시간복잡도 관리가 중요해 

조금 창의적인 해결 방법을 필요로 했던 문제에요

 

-문제

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

1406번: 에디터

 

-풀이

접근

먼저 가장 쉽게 떠올릴 수 있는 풀이는 바로 리스트를 이용한 풀이에요.

 

-L : 주목하고 있던 인덱스 값을 1만큼 줄인다.

-D : 주목하고 있던 인덱스 값을 1만큼 키운다.

-B : 주목하고 있던 인덱스의 원소를 삭제한다. 

-P $: 현재 인덱스의 자리에 $ 문자를 삽입한다. 

 

하지만 이러한 경우에 리스트에 원소를 삽입하거나 삭제하는 method의 시간 복잡도가 O(n)이기에 

최종적인 소스코드의 시간복잡도가 O(n^2)이 되어 시간 초과가 날 수도 있어요.

 

그래서 조금 더 단순한, list의 append, pop 메소드 만을 사용할 수 있는 방법을 찾아야 했어요.

 

완성

리스트를 두개를 선언해요.

하나는 forward, 다른 하나는 backward.

forward 는 커서보다 앞에 있는 문자들을 차례로 저장해요.

즉, 초기에는 주어진 문자열이 그대로 forward에 들어가요.

 

backward는 커서 뒤에 있는 문자열을 저장해요.

그래서, 커서가 왼쪽으로 이동하면 backward는 forward.pop()을 받아들여요

반대로 커서가 오른쪽으로 이동하면 backward에 가장 나중에 들어온 값을  forward에 입력해줘야 해요.

 

이 두 리스트를 이용해 문자 삭제, 문자 삽입 또한 forward.pop(), forward.append()로 해결할 수 있어요.

 

주의해야할 것은 backward에는 우리 생각의 역순으로 문자가 저장되어 있기에 마지막에 reverse 메서드를 이용해 최종 문자열을 완성해주어야 해요. 

 

-소스코드

forward = list(input())
backward = []

import sys
input = sys.stdin.readline

c = int(input())

for _ in range(c):
    com = list(map(str, input().split()))
    
    if com[0] == 'L':
        if forward:
            a = forward.pop()
            backward.append(a)
    elif com[0] == 'D':
        if backward:
            a = backward.pop()
            forward.append(a)
    elif com[0] == 'B':
        if forward:
            forward.pop()
    else:
        forward.append(com[1])
backward.reverse()      
result = forward + backward

print(''.join(result))