[BOJ #1406] 에디터 (Python)

1406번: 에디터

 

겉으로 보기에 그냥 입출력 문제 같다.

처음에 무지성으로 코드를 작성한 내용이다. 

 

처음에 짠 코드

import sys
inputStr = sys.stdin.readline().strip()
count = int(sys.stdin.readline().strip())

cursor = len(inputStr)

for iter in range(count):
    command = sys.stdin.readline().strip().split(' ')
    if(command[0]=='L'):
        if(cursor == 0):
            continue;
        else:
            cursor = cursor - 1
    elif(command[0] == 'D'):
        if(cursor == len(inputStr)):
            continue;
        else: cursor = cursor + 1
    elif(command[0]=='B'):
        if(cursor == 0):
            continue;
        else:
            inputStr = inputStr[0:cursor-1] + inputStr[cursor:]
            cursor = cursor - 1
    else:
        inputStr = inputStr[0:cursor] + command[1] + inputStr[cursor:]
        cursor = cursor + 1
print(inputStr)

정말 문제를 코드로 그대로 옮겨왔다 싶을 정도로 짰다. 

1. L이 들어오면 커서 낮추고
2. D가 들어오면 커서 높이고,,
,,,,

시간제한이 걸려있다는 사실을 크게 신경을 안 쓴 나머지, 저 코드로는 시간초과가 난다. 

 

 

이 문제를 풀기 위해서는 파이썬 연산의 시간 복잡도를 대충은 알고 있어야 한다. 

파이썬의 리스트연산 관련해서 시간 복잡도를 다시 복기해 보자!

 

Operation	Time
list[i]	O(1)
list[i]=0	O(1)
len(list)	O(1)
list.append(5)	O(1)
list.pop()	O(1)
list.clear()	O(1)
list[a:b]	O(b-a)
list.extend(...)	O(len(...))
list1 == list2	O(N)
list[a:b] = k	O(N)
del list[i]	O(N)
x in list	O(N)
list.copy()	O(N)
list.remove(...)	O(N)
list.pop(idx)	O(N)
min(list) or max(list)	O(N)
list.reverse	O(N)
list.sort()	O(N logN)
k*list

내가 기존에 사용했던 것은 slicing으로,, 비교적 나쁜 시간 복잡도를 가지고 반복문을 돌리고 있었다. 

그래서 (파란색으로 칠해둔) O(1)의 최적의 시간복잡도를 보여주는 append와 pop을 이용해서 구현을 해보았다. 

 

 

수정 본

import sys
leftStack = list(input())
rightStack = []
count = int(sys.stdin.readline().strip())

for iter in range(count):
    command = sys.stdin.readline().strip().split(' ')
    if(command[0] == 'L'):
        if(len(leftStack) > 0) : rightStack.append(leftStack.pop())
    elif(command[0] == 'D'):
        if(len(rightStack) > 0): leftStack.append(rightStack.pop())
    elif(command[0] == 'B'):
        if(len(leftStack) > 0): leftStack.pop()
    else: leftStack.append(command[1])

print(''.join(s for s in leftStack+list(reversed(rightStack))))

일단 cursor라는 변수가 없어져서 코드가 간결해졌다. 

커서를 기준으로 왼쪽에 있는 문자열들을 leftStack에, 오른쪽에 있는 문자열들을 rightStack에 넣어두며 pop과 append만 해도되도록 구현하였다. 

 

command L

커서를 왼쪽으로 이동하면, 커서 기준 왼쪽의 문자열은 하나줄어들고, 오른쪽의 문자열은 왼쪽에서 줄어든 문자가 하나 추가된다. 

command D

커서를 오른쪽으로 이동하면, 커서 기준 오른쪽의 문자열은 하나 줄어들고, 왼쪽의 문자열은 오른쪽에서 줄어든 문자가 하나 추가된다.

command B

왼쪽의 문자열을 하나 삭제

command P

왼쪽에 문자열을 하나 추가

 

구현 자체는 간단하다. 

 

 

사용된 파이썬 문법

reverse vs reversed

reverse

+ list 타입에서 제공하는 함수이다. 

+ reverse된 값을 반환하지 않고, list자체를 바꾼다. 

+ list 자료형에만 사용 가능하며, dictionary, tuple, str에서는 사용이 불가능하다. 

list.reverse()

 

reversed

+ 내장함수로 list에서 제공하는 함수가 아니다. 

+ reverse된 값을 반환한다. list 자체를 바꾸지 않는다.

+ list, tuple, str에서 사용이 가능하다. 다만, dictionary에서는 여전히 사용하지 못한다.

reversed(list)

 

 

join

리스트의 모든 요소들을 문자열로 변환

result = ''.join(s for s in list)

숫자가 포함된 리스트의 모든 요소들을 문자열로 변환

result = ''.join(str(s) for s in list)

 

 

시간복잡도를 고려해야하는 입출력 문제

list자료형의 시간복잡도를 고려해야하는 입출력 문제는 다음 문제도 있다. 

10845번: 큐