[Python] 1407번: 에디터 풀이

---

백준 풀이

1407번: 에디터 풀이

---

 

 

 

문제 Link: https://www.acmicpc.net/problem/1406

1406번: 에디터

 

 

문제 설명

 

 

풀이 과정

제가 처음 접근했던 방식은 단순하게 string을 사용하여 관리를 하고, 별도로 index라는 변수를 사용하여 커서를 구현했었습니다. 리스트를 사용하려다가 string으로 관리하는 것이 더 빠르기 때문에 string으로 구현하였습니다. 코드는 다음과 같습니다.

# github link: https://github.com/dubini0/progamming_stuff/blob/main/baekjoon/%5B0%5D%200-4999/1406_%EC%97%90%EB%94%94%ED%84%B0_failed.py

import sys

string = sys.stdin.readline().strip()
n = int(sys.stdin.readline())
index = len(string)

for i in range(n):
    args = sys.stdin.readline().split()
    # print(args)
    if args[0] == "P":
        string = string[:index] + args[1] + string[index:]
        index += 1
    elif args[0] == "L":
        if index == 0:
            continue
        else:
            index -= 1
    elif args[0] == "D":
        if index == len(string):
            continue
        else:
            index += 1
    elif args[0] == "B":
        if index == 0:
            continue
        string = string[:index-1] + string[index:]
        index -= 1
    #print(string)

print(string)

 

이렇게 해도 상관은 없는데, 시간초과가 발생합니다. (17~18%에서 시간초과가 발생합니다.)

 

제가 현재 작성한 코드의 경우, O(n)의 시간복잡도가 발생합니다. (삭제/추가하는 과정)

따라서 문제를 해결하기 위해서는 O(logn)이나 O(1)으로 줄여야 문제를 풀 수 있을 것이라고 생각했습니다.

 

결론적으로 linked list / stack 등을 사용하는 것이 효율적일 것이라고 판단하였고, 저는 2개의 stack을 만들어 구현했습니다. 각각 stack1과 stack2로 나누어, stack1은 커서 기준으로 왼쪽, stack2는 커서 기준으로 오른쪽의 상황으로 만들었습니다.

 

이렇게 문제풀이를 한 이유는 시간복잡도가 O(1)인 append()와 pop()을 사용하기 위함이었습니다. 따라서 stack2도 보면 커서와 가장 가까운 문자가 list의 끝에 있는 것을 확인할 수 있습니다. (del[i]를 사용할 경우 시간복잡도가 O(n))

 

따라서 다음과 같이 다시 코드를 작성할 경우 문제를 풀 수 있습니다.

 

import sys

stack1 = list(sys.stdin.readline().strip())
stack2 = []
n = int(sys.stdin.readline())

for i in range(n):
    args = sys.stdin.readline().split()
    # print(args)
    if args[0] == "P":
        stack1.append(args[1])
    elif args[0] == "L":
        if stack1:
            stack2.append(stack1.pop())
    elif args[0] == "D":
        if stack2:
            stack1.append(stack2.pop())
    elif args[0] == "B":
        if stack1:
            stack1.pop()
    #print(string)

stack1.extend(reversed(stack2))
print(''.join(stack1))

 

 

 

Python 관련 시간복잡도는 다음 글을 참고하면 좋을 것 같네요. https://wayhome25.github.io/python/2017/06/14/time-complexity/

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그