문제 분석

키보드 입력을 받아 커서를 좌우로 움직이고 커서 앞의 문자를 삭제하거나 삽입하여 문자열을 편집하는 간단한 문제다. 그런데 시간제한이 0.3초밖에 되지 않아 insert나 remove등 O(n)의 복잡도를 가지는 메소드를 사용하면 시간초과가 발생한다. 그래서 풀이를 찾아보던 중 알아두면 좋을 것 같은 아이디어가 있어 가져와 보았다.

Key idea

커서가 가리키는 위치에 삽입/삭제를 한다는 생각으로 구현하면 커서의 위치를 인덱스로 관리하고 커서의 위치에 insert하거나 remove할 수 있지만, 각 명령마다 O(n)이 소모되어 시간제한에 걸린다.

따라서 시간을 줄이기 위해서는 커서를 기준으로 앞 문자열과 뒤 문자열을 분리하여 관리하면 insert와 remove없이 구현이 가능하다. 예를 들어 "abcd"라는 문자열에 커서가 b뒤에 있으면 str1 = ab, str2 = cd로 두고 각 명령을 아래와 같이 처리하면 된다.

1. 커서 앞으로 이동 : str1의 마지막 문자를 str2로 이동(a | bcd)
2. 커서 뒤로 이동 : str2의 맨 앞 문자를 str1으로 이동(abc | d)
3. 커서 앞의 문자 삭제 : str1의 마지막 문자 삭제(a | cd)
4. 커서 앞에 문자 x 삽입 : str1의 마지막에 x추가(abx | cd)

위의 방법으로 구현하면 문자열의 맨 앞 혹은 맨 뒤 문자만 다루기 때문에 각 연산에 O(1)만큼의 시간만이 소요된다.

Solution

위의 아이디어 대로 구현하여 insert와 remove를 사용하지 않고 append, pop만을 사용하여 문제를 해결하였다.

str1 = list(sys.stdin.readline().strip())
n = int(sys.stdin.readline())
str2 = []

for _ in range(n):
    cmd = sys.stdin.readline().strip().split(" ")
    if cmd[0] == 'L':
        if str1:
            str2.append(str1.pop())
    elif cmd[0] == 'D':
        if str2:
            str1.append(str2.pop())
    elif cmd[0] == 'B':
        if str1:
            str1.pop()
    elif cmd[0] == 'P':
        str1.append(cmd[1])

str1.extend(reversed(str2))
print("".join(str1))

• BOJ 1406 에디터