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

문제

1406번: 에디터

알고리즘

- 입력받은 문자열 리스트는 커서의 왼쪽에 위치하게 한다.

- 커서 오른쪽에 있는 요소들은 새로운 리스트에 담는다.

- 커서를 왼쪽으로 한 칸 옮기기 위해 문자열 리스트에 하나를 빼고 뺀 값을 커서 오른쪽에 있는 요소를 담는 리스트에 추가한다.

- 위 방법과 같이 커서 왼쪽에 있는 요소는 문자열 리스트에, 커서 오른쪽에 있는 요소는 다른 리스트에 넣는다.

- 모든 명령을 수행하고 커서 왼쪽에 있는 리스트를 출력하고 오른쪽에 있는 리스트는 거꾸로 바꿔 출력한다.

코드

import sys

temp = list(map(str, sys.stdin.readline().strip()))
stack = [] # 커서 오른쪽에 있는 요소
n = int(sys.stdin.readline())
for i in range(n):
    # temp 맨 오른쪽에 있는 위치가 커서의 위치
    order = list(map(str, sys.stdin.readline().split()))

    # 커서를 왼쪽으로 한칸 옮김
    if order[0] == "L" and temp:
        stack.append(temp.pop())

    # 커서를 오른쪽으로 한칸 옮김
    elif order[0] == "D" and stack:
        temp.append(stack.pop())

    # 커서 왼쪽에 있는 문자를 삭제
    elif order[0] == "B" and temp:
        temp.pop()

    # 커서 왼쪽에 문자를 추가
    elif order[0] == "P":
        temp.append(order[1])

# 문자열과 커서 오른쪽에 위치해야할 요소를 출력
print("".join(temp + list(reversed(stack))))

 

실패한 코드(시간 초과)

실패한 코드에서는 시간 복잡도가 O(N)인 insert(), del 함수를 사용했고

위에 성공한 코드에서는 시간 복잡도가 O(1)인 append(), pop() 함수를 사용했다.

import sys

temp = list(map(str, sys.stdin.readline().strip()))
n = int(sys.stdin.readline())
temp.append("A")
for i in range(n):
    order = list(map(str, sys.stdin.readline().split()))


    index = temp.index('A')

    # 커서를 왼쪽으로 한칸 옮김
    if order[0] == "L":
        if index == 0:
            continue
        else:
            temp.insert(index - 1, "A")
            index += 1
            del temp[index]

    # 커서를 오른쪽으로 한칸 옮김
    elif order[0] == "D":
        if index == len(temp) - 1:
            continue
        else:

            temp.insert(index + 1, "A")
            del temp[index]

    # 커서 왼쪽에 있는 문자를 삭제
    elif order[0] == "B":
        if index == 0:
            continue
        else:
            del temp[index - 1]
    else:
        temp.insert(index, order[1])

temp.remove("A")
print("".join(temp))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법