[백준] 에디터 1406.python

 문제

- 입력받은 문자열을 명령어를 통해 수정하는 문제이다.

 

- 커서

   _ a _ b _ c _ d _

   문자열의 길이(L) + 1의 위치 개수를 가진다.

 

- 커서이동: L(왼쪽), D(오른쪽)

- 문자: B(커서 왼쪽 삭제), P x('x' 문자를 커서 왼쪽에 삽입)

 

 

 해설 및 코드

- 처음에는 list의 insert, pop을 이용해서 문자열의 in/out을 실행했다.

 

- 시간초과 발생

  list의 insert(N), pop(N)의 시간복잡도는 O(n)을 가진다.

 

 

해결방법

 

- stack, pop의 경우 in/out의 시간복잡도는 O(1)이다.

 

- 내가 원하는 위치(N)에 숫자를 넣기 위해서는 커서를 기준으로 left / right로 stack을 나눈다.

 

- python의 경우 stack이든 queue든 list로 구현이 가능하므로, list에서 append, pop 명령어만을 이용해 코드를 작성한다.

 

 

import sys


# 커서를 기준으로 stack을 나눈다. (left / 커서 / right)
# 처음 커서의 위치는 입력받은 문자열의 맨 끝이므로, left에 문자열을 모두 입력받는다.

left = list(sys.stdin.readline().rstrip())
right = []

# 명령어 개수
M = int(sys.stdin.readline().rstrip())


for _ in range(0, M):
    cmd = list(sys.stdin.readline().rstrip().split())

    if cmd[0] == 'L':
    	# 커서가 왼쪽으로 이동하므로, left의 제일 끝에 있는 숫자는 오른쪽으로 옮겨준다.
        if len(left):
            mv = left.pop()
            right.append(mv)
            
		# 커서가 오른쪽으로 이동하므로, right의 제일 앞 숫자(list에서는 제일 끝)를 left의 제일 끝으로 옮긴다.
        # pop()은 제일 마지막을 꺼낸다. -> right의 리스트는 거꾸로 삽입되어 있다.
        # a b c _ d e f 였을 때, left는 a, b, c로 담겨있고, right는 f, e, d 순서로 담겨있다.
    elif cmd[0] == 'D':
        if len(right):
            mv = right.pop()
            left.append(mv)

		# 왼쪽을 삭제하므로 왼쪽 stack에서 pop()을 실행하면 된다.
    elif cmd[0] == 'B':
        if len(left):
            left.pop()
            
		# left의 제일 뒤에 삽입한다.
    elif cmd[0] == 'P':
        left.append(cmd[1])
    
# right는 뒤에서부터 출력한다.
print(''.join(left+right[::-1]))

 

 

 

Python 문법 정리

- list -> 문자열 변환

''.join(list)