[Python] 백준 #1406 에디터

www.acmicpc.net/problem/1406

1406번: 에디터

시간 초과에 대해 깊게 생각 해볼 수 있었던 문제였다.!

 

List는 메모리 공간을 할당해서 자료를 저장해서 삽입하거나 삭제할때 다른 원소들을 밀거나 당기는 등.. 건들이게됨.

이 문제를 풀기 위해서는 

1. List의 맨 앞,뒤에서만 삽입/삭제 연산을 할 수 있도록 알고리즘 구현하기

2. 다른 원소를 건들일 필요가 없는 자료구조 사용하기

를 생각해야한다

 

시간초과난 첫번째 코드

import time

T=time.time()
s=input()
List=[0]*600001
for i in range(len(s)):
    List[i]=s[i]
pointer = len(s)

n=int(input())
for i in range(n):
    cur=input().split()
    if cur[0]=='L':
        if pointer !=0:
            List[pointer-1],List[pointer]=List[pointer],List[pointer-1]
            pointer=pointer-1
    elif cur[0]=='D':
        if pointer !=len(s):
            List[pointer+1],List[pointer]=List[pointer],List[pointer+1]
            pointer+=1
    elif cur[0] =='B':
        if pointer !=0:
            List[pointer-1]=0
            List.remove(0)
            pointer=pointer-1
    elif cur[0] =='P':
        data=cur[1]
        List.insert(pointer,data)
        pointer+=1
        
#커서랑 비어있는거 지움
List=list(filter(lambda x:x!=0,List))
print(''.join(List))
print(time.time()-T)

시간초과가 나서 덱을 생각해봤다.

 

두개의 덱(스택,큐)를 써서 커서를 가운데로 놓고 생각해보았다.

 

#readline()에 개행 문자 포함된걸 생각못하고 계속 왜 틀렸는지 삽질했다...ㅋ
#아무래도 sys 모듈 쓸 수 있는 파이참으로 넘어가야할듯


from collections import deque
import sys

que_1=list(sys.stdin.readline().strip())
que_2=deque()
n=int(sys.stdin.readline())
    
for i in range(n):
    com=sys.stdin.readline().split()
    if com[0]=='L':
        if que_1:
            que_2.append(que_1.pop())        
    elif com[0]=='D':
        if que_2:
            que_1.append(que_2.pop())        
    elif com[0]=='B':
        if que_1:
            que_1.pop()
    elif com[0]=='P':
        que_1.append(com[1])
        
print(''.join(list(que_1)+list(reversed(que_2))))

 

*시간 복잡도에 관한 생각*

wiki.python.org/moin/TimeComplexity

List 사용

deque 사용

당연히 deque를 사용했을 때 더 빠를 것이라고 생각했는데.. 구글링을 통해 검색해보니 python에서 list의 경우에는 동적 array로 구현되어 있고 deque의 경우 양방향 linked-list의 형태로 구현되었음을 알수있다.

따라서 stack의 동작을 생각해보면 동적 array와 linked-list의 append와 pop 연산은 둘다 O(1)임을 알 수 있다.

list가 더 빠른이유는 생성할때 동적 array의 경우가 더 빠르고, pop과 append 연산시에 같은 시간복잡도 일지라도 linked-list가 자신과 연결된 node의 주소값을 저장하는 과정과 linked-list의 끝을 가리키는 값 수정 등 여러 추가사항이 있어서 조금 더 느린것으로 예상된다.

deque가 list보다 빠른 경우는 위의 글에서 보여주듯이 두 배열의 맨 앞에 추가하는 연산인 deque의 appendleft 와 list의 insert이다.

위의 경우에는 deque의 시간복잡도는 O(1) 이고, list는 동적 array이므로 모든 요소를 왼쪽으로 옮기는 연산 때문에 O(n)의 시간복잡도를 갖는다.

따라서 스택을 활용할때는 list를, 큐를 활용할때는 deque를 사용하는것이 유리할것으로 보인다.