1406번 에디터

문제 출처 : https://www.acmicpc.net/problem/1406

문제 자체는 해부해봤을 때 심플. L,D는 위치(index)를 결정하기 위한 command이며, B,P는 del,insert 를 구현하는 command이다. 결국 이 문제를 해석하면 del, insert를 효과적으로 빠르게 구현하는 방식을 아는지 물어보는 것 같았다.
먼저 떠오른 것은 연결리스트. 왜냐하면 연결리스트는 삽입과 삭제에 있어 리스트보다 더 효과적이고 강력하니까! 그러나 연결리스트를 직접 만들기는 힘들어 이를 이용한 list,str의 속성을 이용해 풀기로 하였다.

import sys

line = [0]+list(sys.stdin.readline().rstrip("\n"))
N = int(sys.stdin.readline().rstrip("\n"))
c = len(line)-1

for _ in range(N) :
    command = sys.stdin.readline().rstrip("\n").split()
    if command[0]=="L" :
        if c==0:
            continue
        c-=1
    elif command[0]=="D" :
        if c==len(line)-1 :
            continue
        c+=1
    elif command[0]=="B":
        if c==0 :
            continue
        line = line[:c]+line[c+1:]
        c-=1
    elif command[0]=="P" :
        line = line[:c+1]+[command[1]]+line[c+1:]
        c+=1
print("".join(line[1:]))

결과는 시간 초과. str로도 바꿔봤지만 결과는 마찬가지. 내가 짠 것보다 물론 더 간단하게 풀수도 있겠지만 더이상 간단하게 짤수 없을것같고 알고리즘보다는 이 문제에선 이론을 알아야겠다 라는 생각이 들어서 결국 해답지를 편다.

찾아보니 a[i:j]라는 뜻은 리스트 a를 i부터 j까지 슬라이싱 한다는 것이기 때문에 k개의 객체를 조회화므로 시간복잡도가 k이다.

문자열 슬라이싱이 비교적 빠른 것은 맞으나 이 문제에서는 O(1)로 더 효율적인 방식이 가능했다.

---

두 개의 STACK을 이용한다. 결국 순차적!!이기 때문에 STACK의 특성을 적용가능.
근데 사실 위에 것도 상당히 빠를 거라 생각했는데 왜 시간초과인지... O(n) 아닌가?

import sys

line = list(sys.stdin.readline().rstrip("\n"))
N = int(sys.stdin.readline().rstrip("\n"))
c = len(line)-1
stack=[]

for _ in range(N) :
    command = sys.stdin.readline().rstrip("\n").split()
    if command[0]=="L" :
        if not line :
            continue
        stack.append(line.pop())
    elif command[0]=="D" :
        if not stack :
            continue
        line.append(stack.pop())
    elif command[0]=="B":
        if not line :
            continue
        line.pop()
    elif command[0]=="P" :
        line.append(command[1])
print("".join(line+stack[::-1]))

더 빨리 푼 사람도 있어서 조금 더 개선해보자.

알골은 동일한데 어느 이론적인 부분에서 차이가 발생하는 거지?