[알고리즘][파이썬] 백준_1406_에디터

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

1406번: 에디터

임의의 문자열을 입력하고,

커서를 조작하는 명령어,

"L(왼쪽 한칸 이동), D(오른쪽 한칸 이동), B(왼쪽 문자 삭제), P $($라는 문자 왼쪽에 추가)"를

M개 입력한 결과를 출력해야 한다.

 

백준 알고리즘 강의 초급에 해당하는 문제인데,

시간제한 때문에 무척 애를 먹었다(이게 초급이라니).

 

---

시간 초과

# insert or slice 이용(결과: 시간 초과)
import sys

def L():
    global cur
    if cur > 0:
        cur -= 1

def D():
    global ipt
    global cur
    if len(ipt) > cur:
        cur += 1

def B():
    global ipt
    global cur
    if len(ipt) == 1:
        pass
    elif cur > 0:
        del ipt[cur-1]
        cur -= 1

def P(chr):
    global ipt
    global cur
    # ipt.insert(cur, chr) # insert의 시간 복잡도 O(N)
    ipt = ipt[:cur] + list(chr) + ipt[cur:] # Slice의 시간 복잡도 O(N)
    cur += 1

ipt = list(sys.stdin.readline().strip())
M = int(sys.stdin.readline().strip())

cur = len(ipt)

cmd = ''
add = ''
for _ in range(M):
    tmp = sys.stdin.readline().strip() # strip 함수 이용 불필요한 개행문자 제거
    space = tmp.find(' ')
    if space == -1:
        globals()[tmp]()
    else:
        cmd, add = tmp[:space], tmp[space+1:]
        globals()[cmd](add)

print(''.join(ipt))

 

위 코드의 실행 결과 예제에 대한 출력은 정확하게 이루어 졌다.

하지만 제출 결과는 시간 초과!

아무리 고민해봐도 insert와 slice를 대체할 방법이 떠오르지 않았다.

 

구글링을 통해 명쾌한 풀이를 접했다.

 

---

맞았습니다!

# 제출 코드(결과: 맞았습니다!)
import sys

left_move = list(sys.stdin.readline().strip()) # strip 함수 이용해 불필요한 개행문자를 제거한다.
right_move = []

M = int(sys.stdin.readline())

for _ in range(M):
    cmd = list(sys.stdin.readline())
    if cmd[0] == 'L':
        if left_move:
            right_move.append(left_move.pop())
    elif cmd[0] == 'D':
        if right_move:
            left_move.append(right_move.pop())
    elif cmd[0] == 'B':
        if left_move:
            left_move.pop()
    else:
        left_move.append(cmd[2])

left_move.extend(reversed(right_move))
print(''.join(left_move))

 

위 코드의 장점은,

첫 번째, for 문 하나로 명령어 구현 가능.

기존에는 명령어 L, D, B, P$를 각각 함수로 구현했는데,

for 문 안에서 if 조건문으로 간단히 구현 가능했다.

 

두 번째, 리스트의 pop, append 함수로 구현 가능.

시간복잡도 O(1)에 해당하는 함수로 구현이 가능했다.

 

세 번째, 명령어 문자열의 0번 주소이용.

기존에는 globals함수를 이용했는데,

문자열의 0번 주소로 명령어와 간단히 매핑할 수 있었다.

 

네 번째, 빈 리스트가 False라는 점을 이용.

커서가 문자열의 왼쪽 또는 오른쪽 끝으로 이동 한 경우,

L, D 명령어로 더 이상 이동하지 못하게 하는 코드를

빈 리스트가 False라는 점을 이용해

if 조건문 안에서 간단히 구현했다.

 

다섯 번째, 내장 함수 reversed의 사용.

이 효율적인 코드를 소개한 블러그에서 접한 내용인데,

리스트 함수 reverse의 경우 빈 리스트일 때 TypeError을 띄운다.