[Python/파이썬] 백준 알고리즘 1406번 - 에디터

 

 

 

<풀이 1 - 시간 초과>

string = list(input())
N = len(string)
M = int(input())
cursor = N

for _ in range(M):
    command = input().split()
    if command[0] == "L":
        if cursor > 0:
            cursor -= 1
    elif command[0] == "D":
        if cursor < N+1:
            cursor += 1
    elif command[0] == "B":
        if cursor > 0:
            string.pop(cursor-1)
            cursor -= 1
    elif command[0] == "P":
        string.insert(cursor, command[1])
        cursor += 1

for s in string:
    print(s, end='')

처음에 위와 같이 작성했는데 시간 초과가 떴다. 이 문제가 제한 시간이 박한 편이라 더 cost가 낮은 방법을 찾아야 했다.

insert()의 시간복잡도는 O(N)이라 이렇게 하면 안됐다.

시간복잡도 O(1)을 갖는 append()와 pop()만으로 문제를 해결해야 했다.

구글링을 통해 알아낸 방법은 stack을 두 개 사용하는 방법이다.

 

 

<풀이 2 - 성공>

위와 같이 Stack 두 개를 놓고 커서는 Stack_1의 top이라고 생각하는 것이다.

커서가 왼쪽으로 이동하면 Stack_1의 값을 pop해서 Stack_2으로 append하고 커서가 오른쪽으로 이동하면 Stack_2의 값을 pop해서 Stack_1으로 append하는 방식이다.

# stack 두 개를 이용해 시간 단축
# append, pop은 O(1)이다.
import sys

stack_1 = list(sys.stdin.readline().rstrip())
stack_2 = []
N = len(stack_1)
M = int(input())

for _ in range(M):
    command = sys.stdin.readline().split()
    if command[0] == "L" and stack_1:
        stack_2.append(stack_1.pop())
    elif command[0] == "D" and stack_2:
        stack_1.append(stack_2.pop())
    elif command[0] == "B" and stack_1:
        stack_1.pop()
    elif command[0] == "P":
        stack_1.append(command[1])

print("".join(stack_1 + list(reversed(stack_2))))

if문에서 stack_1은 stack_1이 비어있지 않다면 true가 되어 들여쓰기 된 코드를 실행하게 된다.

마지막에 stack_2는 뒤집힌 꼴이기 때문에 reversed를 해줘서 출력해준다.

(참고로 sys로 입력을 받지않으면 python3에서는 시간초과 뜬다. sys.stdin.readline() 쓰자)

 

 

 

<핵심 정리>

1. 커서를 Stack 두 개를 가지고 표현할 수도 있다.

2. append(), pop() -> O(1)   /   insert() -> O(n)

3. 리스트를 for문 없이 출력할 때 "".join(리스트)를 사용할 수 있다.