백준 1406

문제

https://www.acmicpc.net/problem/1406

코드

처음 푼 코드는 다음과 같다.

import sys

str = sys.stdin.readline().rstrip()
N = int(sys.stdin.readline())

loc = len(str)

for i in range(N):
    cmd = sys.stdin.readline().rstrip()
    
    if cmd[0] == 'L':
        if loc > 0:
            loc -= 1
    elif cmd[0] == 'D':
        if loc != len(str):
            loc += 1
    elif cmd[0] == 'B':
        if loc > 0:
            str = str[:loc - 1] + str[loc:]
            loc -= 1
    elif cmd[0] == 'P':
        str = str[:loc] + cmd[2] + str[loc:]
        loc += 1

print(str)

시간 초과가 떴다.

(시간 초과의 경우, 시간 초과가 뜨기 전까지는 정답이지만 이것이 모든 케이스에 대한 정답인지는 알 수 없는 것 같다.)

아직 시간 복잡도를 어렵게 느껴서..
위의 코드가 시간 초과를 제외하곤 문제가 없다고 생각하는데, 시간 초과를 어떻게 해결해야 할지 막막했다.

이후 다른 사람의 풀이를 찾아봤는데,
시간 초과가 뜨면 '자료 구조'를 사용하는 것이 하나의 방법이라고 한다.

수정된 코드(정답)는 아래와 같다.

import sys

left = list(sys.stdin.readline().rstrip())
right = []

for i in range(int(sys.stdin.readline())):
    cmd = sys.stdin.readline().rstrip()
    
    if cmd[0] == 'L':
        if left:
            right.append(left.pop())
    elif cmd[0] == 'D':
        if right:
            left.append(right.pop())
    elif cmd[0] == 'B':
        if left:
            left.pop()
    elif cmd[0] == 'P':
        left.append(cmd[2])
        
right.reverse()
print(''.join(left + right))

stack을 2개 사용한 풀이이고,
커서를 기준으로 왼쪽 문자열과 오른쪽 문자열을 구분해서 풀었다.

이 코드를 제출하기 전에 여러 번 틀렸는데 그 이유는..
1)
디버깅 할 때 썼던 print()를 지우지 않고 그대로 제출했기 때문

2)
print(left + reverse(right))라는 코드에서,
reverse() 메서드가 리스트를 역순으로 뒤집는 기능을 수행하지만,
reverse() 메서드는 리스트를 뒤집기만 하고 새로운 리스트를 반환하지 않는다.
그래서 right.reverse()가 None을 반환하기 때문에 left + (None)이라 에러가 뜬다.

3)
append() 대신 insert()를 써도 시간 초과가 떴다.
시간 복잡도를 비교하면 다음과 같다.
append(): O(1)
insert(): O(N)

기타

오랜만에 문제를 풀었다. 방학 때 꾸준히 풀자.

그리고 디버깅 할 때 print()로 중간 결과를 확인하는 것은 좋은 방법인 것 같다.