[백준][문제 풀기] 알고리즘 기초 1/2 - 1406 에디터

이 문제는 함정이 있다.
자료구조를 제대로 이용하지 않으면 풀 수가 없도록 되어 있는 문제이다.
왜 그런지 한번 살펴보자.

---

실패한 코드

import sys


if __name__ == "__main__" :

    # 데이터를 잘 받자!
    target_str = sys.stdin.readline().strip()
    ppos = len(target_str)

    N = int(sys.stdin.readline())
    procs = []
    for i in range(N) :
        # 데이터를 잘 받자
        proc = sys.stdin.readline().strip().split()

        if proc[0] == "L" :
            ppos = max(ppos - 1, 0)
        elif proc[0] == "D" :
            ppos = min(ppos + 1, len(target_str))
        elif proc[0] == "B" :
            if ppos > 0 :
                target_str = "".join([target_str[:ppos-1], target_str[ppos:]])
                ppos -= 1
        elif proc[0] == "P" :
            new_char = proc[1]
            target_str = "".join([target_str[:ppos], new_char, target_str[ppos:]])
            ppos += 1


    print(target_str)

• 위 코드가 제일 처음 작성한 코드이다. 처음 작성하고나서 왜 이 문제가 자료구조 문제인거지? 하고 생각했었다. 문제의 시간제한이 0.3초이고 문자열 길이가 최대 600,000자 라는 점을 보고 깨달았어야했다...

• 사용한 python 기능 중에서 심각한 performance저하를 야기하는게 있나? 싶어서 몇가지를 고쳐봤지만 마찬가지였다.

• 아래는 다른 사람의 풀이를 참고해서 해법을 찾은 코드다

성공한 코드

import sys


if __name__ == "__main__" :

    # 데이터를 잘 받자!
    str_l = [v for v in sys.stdin.readline().strip()]
    ppos = len(str_l)
    str_r = []

    N = int(sys.stdin.readline())
    procs = []
    for i in range(N) :
        # 데이터를 잘 받자
        proc = sys.stdin.readline().strip().split()

        if proc[0] == "L" :
            if len(str_l) > 0 :
                tmp = str_l.pop()
                str_r.append(tmp)
        elif proc[0] == "D" :
            if len(str_r) > 0 :
                tmp = str_r.pop()
                str_l.append(tmp)
        elif proc[0] == "B" :
            if len(str_l) > 0 :
                tmp = str_l.pop()
        elif proc[0] == "P" :
            new_char = proc[1]
            str_l.append(new_char)

    target_str = str_l + str_r[::-1]
    print("".join(target_str))

• 이렇게 하니 통과된다. 이런 방법은 정말 상상도 못했는데, 아직 많이 부족하다는 것을 느낀다.