에디터 백준 1406번 연결리스트

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

문제

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 ‘커서’라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

L D B P $

커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)
(삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임)
$라는 문자를 커서 왼쪽에 추가함

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

---

해당 문제의 경우 C,C++로 풀때 연결리스트를 사용해서 푸는 문제인데 파이썬으로 풀기 위해서 그냥 리스트로 반환해버리고 구현으로 접근해서 문제를 풀었다. 커서의 위치를 확인하면서 조건따라서 커서를 옮기거나 삭제, 추가를 구현 할려고 한다.

string = list(input())
#string = list('abcd')
now_loc = len(string)

num = int(input())
#num = 3

for i in range(num):
    func = input()
    check_len = len(func)
    if check_len!=1:
        oper,stg = func.split()
        string.insert(now_loc,stg)
        now_loc+=1
    else:
        if func=='L':
            if now_loc!=0:
                now_loc-=1
        elif func=='D':
            if now_loc!=len(string):
                now_loc+=1
        elif func=='B':
            if now_loc!=0:
                del string[now_loc-1]
                now_loc-=1
    
print(''.join(string))

문제는 모든 과정은 N으로 끝나는 것 같았는데 아무래도 시간초과가 나왔다.

문자열과 몇번 행동을 할지는 둘째치고 들어오는 문자가 P인것과(인자가 2개) 아닌것(인자가 1개)으로 구분이 되는데 이들을 구분할 방법이 마땅히 없어서 그냥 입력을 받고 문자열이 1개가 넘는지를 보았다. 그래서 해당 위치에 삽입을 하고 커서는 1 증가를 하고

인자를 옮길 경우에는 커서가 0의 위치가 아니라면 왼쪽으로 옮기고 string의 길이와 같은게 아니라면 1을 추가를 해주었고

리스트에서 특정 인덱스에 있는 인자를 지우기 위해서 del을 사용하고 커서도 한칸 이동했다.

대충 예시로 나온 테스트케이스는 모두 정답이 나왔지만 시간 제한이 자바와 C++에서 2초로 엄격하게 제한이 되어 있는데 다른 방법을 고민을 해봐야 겠다.