1406번 에디터

문제

1406번: 에디터

 

나의 풀이(시간 초과)

s = input()
n = int(input())

s_list = list(s)
cur = len(s_list)
for _ in range(n):
    user_commend = input()

    if user_commend[0] == 'L' and cur != 0:
        cur -= 1

    if user_commend[0] == 'D' and cur != len(s_list):
        cur += 1

    if user_commend[0] == 'B' and cur != 0:
        if cur == 1:
            s_list = s_list[1:]
            cur = 0
        elif cur == len(s_list):
            s_list = s_list[:-1]
            cur -= 1
        else:
            s_list = s_list[:cur-1] + s_list[cur:]
            cur -= 1

    if user_commend[0] == 'P':
        half_list = s_list[:cur]
        half_list.append(user_commend[-1])
        s_list = half_list + s_list[cur:]
        if cur != len(s_list):
            cur += 1
            

print(''.join(s_list))

슬라이싱을 하는 것 또한 시간복잡도가 슬라이싱 된 리스트의 길이 만큼 소요된다. 현재 위치인 cur이란 변수를 활용해서 슬라이싱 하는 방식을 생각했지만, 이것도 시간 초과.

 

 

정답 풀이

s_list = list(input())
n = int(input())
stack = []

for _ in range(n):
    user_commend = input()

    if user_commend[0] == 'L' and s_list:
        stack.append(s_list.pop())

    if user_commend[0] == 'D' and stack:
        s_list.append(stack.pop())

    if user_commend[0] == 'B' and s_list:
        s_list.pop()

    if user_commend[0] == 'P':
        s_list.append(user_commend[-1])
            

print(''.join(s_list + list(reversed(stack))))

스택 객체를 하나 더 생성하여 현재 위치가 항상 마지막 인덱스에 위치하도록 만듦.

pop() 메소드는 안에 인덱스를 사용한다면 O(n)시간 복잡도를 갖고있기에 상수시간의 시간 복잡도를 활용하기 위해 현재 위치를 항상 마지막에 위치하도록 다른 스택 리스트에 넣어준다. 그리고 마지막에 해당 리스트를 뒤집어서 원래 리스트와 합쳐주면 된다.

 

리스트를 두개로 쪼개어 생각하다니... 참신하다