[백준/Python] 에디터 1406

알고리즘 분류 : 연결 리스트, 스택

시간복잡도 : O(N)

<접근>

• 시간복잡도 NlogN까지 가능
• 단순 구현을 하면 insert, del에서 O(N)이 쓰이기 때문에 TLE가 발생한다
• insert, del에서 시간복잡도를 줄이기 위해 deque의 popleft, appendleft를 사용한다
• 또한 popleft와 appendleft를 사용하기 위해서, cursor를 기준으로 String을 좌측과 우측으로 분리한다

실패

1. 구현
- TLE, insert와 del을 처리할 방법이 필요

2. 구현
- insert와 del이 O(1)인 deque를 사용
- TLE, deque는 이중 연결리스트로, 중간값에 대해서는 접근이 느리기 때문에 항상 O(1)이 아님

성공

3. 구현
- reference : https://velog.io/@j1min/Python-%EB%B0%B1%EC%A4%80-1406-%EC%97%90%EB%94%94%ED%84%B0-%ED%92%80%EC%9D%B4
- 커서를 기준으로 리스트를 좌,우로 나누어서 deque.popleft, appendleft를 사용한다
- popleft, pop, appendleft, append로 O(1)로 수행가능

코드

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

def input_data():
    string = input().strip()
    m = int(input())
    return string, m

def processing(command):
    c_type = command[0]
    # command를 L,D,B,P로 나눠서 처리
    if c_type == "L":
        # 커서 좌측이 존재한다면 -> 커서가 처음이 아니라면
        if len(leftString) != 0:
            # 커서 좌측 맨끝을, 커서 우측 제일처음으로 옮김
            moved = leftString.pop()
            rightString.appendleft(moved)
    elif c_type == "D":
        # 커서 우측이 존재한다면 -> 커서가 제일 끝이 아니라면
        if len(rightString):
            # 커서 우측 맨 처음을, 커서 좌측 제일 끝으로 옮김
            moved = rightString.popleft()
            leftString.append(moved)
    elif c_type == "B":
        # 커서 좌측이 존재한다면 삭제
        if len(leftString) != 0:
            leftString.pop()
    else:
        # 커서 좌측에 요소 추가
        leftString.append(command[1])

def solution(string, m):
    global leftString, rightString
    # 커서 왼쪽, 오른쪽으로 리스트를 나눈다
    leftString = deque(string)
    rightString = deque()
    # m번의 명령을 실행
    for _ in range(m):
        command = input().split()
        processing(command)
    # 정답 반환
    return ''.join(leftString+rightString)


print(solution(*input_data()))