[BOJ] 1406번 - 에디터

문제

1406번: 에디터

 

🚦 문제 유형

• 자료구조
• 스택 
• 연결 리스트

 

✏️ Solution

이 문제는 시간제한이 0.3초로 매우 짧아서 시간복잡도를 생각하면서 풀어야 한다.

풀이 방법은 3가지를 생각해 볼 수 있다.

1. 입력 문자열 리스트에 커서를 추가해서 명령어 대로 수행
2. 스택 사용 - 커서를 따로 추가하지 않고 2개의 스택으로 명령어 수행
3. 덱 사용 - 커서를 따로 추가하지 않고 1개의 리스트와 1개의 덱으로 명령어 수행

1. 입력 문자열 리스트에 커서를 추가해서 명령어 대로 수행

입력 문자열이 'abcd' 라고 하면 커서를 ' _(underbar)' 로 설정하고 리스트에 추가한 뒤 커서의 현재 위치를 기준으로 명령어를 수행한다.

명령어 L, D, P, P 마다

• 현재 커서 위치 반환(cursor)
• 커서 위치 조건과 비교
• L, D, B, P 명령어 수행

 

이런 식으로 생각해서 코드를 짰고 코드는 다음과 같다.

# 시간초과
# 주의할 점: 리스트의 insert, delete, remove의 시간복잡도는 O(N) 이다.
from collections import deque
import sys

s = list(sys.stdin.readline().rstrip())
n = int(sys.stdin.readline().rstrip())
order = [sys.stdin.readline().rstrip().split(' ') for _ in range(n)]

order_q = deque(order)
s.append('_')

while order_q:
    o = order_q.popleft()   # 명령어
    if o[0] == 'L':
        cursor = s.index('_')   # 현재 커서가 위치하는 곳
        if cursor == 0:  # 현재 커서가 문장의 맨 앞이면
            pass
        else:   # 커서를 왼쪽으로 한 칸 옮김('_'의 위치를 바꿈)
            tmp = s[cursor-1]
            s[cursor-1] = '_'
            s[cursor] = tmp
    elif o[0] == 'D':
        cursor = s.index('_')
        if cursor == len(s)-1:  # 현재 커서가 문장의 맨 뒤이면
            pass
        else:   # 커서를 오른쪽으로 한 칸 옮김('_'의 위치를 바꿈)
            tmp = s[cursor+1]
            s[cursor+1] = '_'
            s[cursor] = tmp
            
    elif o[0] == 'B':
        cursor = s.index('_')
        if cursor == 0:
            pass
        else:
            del s[cursor-1] # 커서 왼쪽에 있는 문자를 삭제함.
    else:   # P
        cursor = s.index('_')
        s = s[:cursor] + list(o[1])+ s[cursor:]
s.remove('_')         
print(''.join(s))

코드는 잘 돌아가지만 문제점은 시간초과이다.

틀린 곳은 없어보였기에 입력 개수에 따른 리스트 처리의 문제라고 생각했고 의심되는 del, index 함수의 시간복잡도를 찾아보니 O(N) 인 것을 알았다. 이 문제에서는 시간이 0.3초로 매우 짧기 때문에 요소를 삭제, 추가하는 부분에서 시간을 많이 줄여야 한다.

 

2. 스택 사용 - 커서를 따로 추가하지 않고 2개의 스택으로 명령어 수행

1번의 문제를 해결할 수 있는 방법은 자료구조를 사용하는 것이다.

커서를 나타내는 어떤 문자열을 추가하는 것 없이 2개의 스택 사이에서 append, pop 하는 것만으로도 구현할 수 있다.

스택 1과 스택 2 중간에 투명다리 위치가 커서라고 보면 이해가 훨씬 쉽다.

코드는 다음과 같다.

# 한개의 리스트 대신 2개의 스택을 사용.
import sys
st1 = list(sys.stdin.readline().rstrip())
n = int(sys.stdin.readline().rstrip())
command = [sys.stdin.readline().rstrip().split(' ') for _ in range(n)]
st2 = []


for cmd in command:
    if cmd[0] == 'L':
        if st1: # 현재 커서가 문장의 맨 앞이면
            st2.append(st1.pop())
    elif cmd[0] == 'D':
        if st2: # 현재 커서가 문장의 맨 뒤이면
            st1.append(st2.pop())
    elif cmd[0] == 'B':
        if st1:
            st1.pop()
    else:
        st1.append(cmd[1])    
        
st1.extend(reversed(st2))   # 스택의 순서 고려
print(''.join(st1))

주의할 점: 스택은 LIFO 구조로 원래 순서로 돌려줘야 하므로 스택 2를 reverse 함수를 부르고 스택 1, 2를 붙여야한다.

만약 reverse를 쓰고 싶지 않다면 deque(덱)을 쓰는 방법도 있다.

3. 덱 사용 - 커서를 따로 추가하지 않고 1개의 리스트와 1개의 덱으로 명령어 수행

방법은 스택과 비슷한데 원소의 삽입, 삭제 명령어만 다르다.

• pop() -> popleft()
• append() -> appendleft()

# 덱(deque) 사용
import sys
from collections import deque

st1 = list(sys.stdin.readline().rstrip())
n = int(sys.stdin.readline().rstrip())
command = [sys.stdin.readline().rstrip().split(' ') for _ in range(n)]
dq = deque([])


for cmd in command:
    if cmd[0] == 'L':
        if st1: # 현재 커서가 문장의 맨 앞이면
            dq.appendleft(st1.pop())
    elif cmd[0] == 'D':
        if dq: # 현재 커서가 문장의 맨 뒤이면
            st1.append(dq.popleft())
    elif cmd[0] == 'B':
        if st1:
            st1.pop()
    else:
        st1.append(cmd[1])    
        
print(''.join(st1 + list(dq)))

 

⚙️ Review

난이도 실버 2인데도 정답 비율이 26% 정도인 것을 보니 생각보다 쉽게 풀 수 있는 문제는 아니었다. 

문제 설명대로 코드를 구현하는 것은 어렵지 않았지만 시간초과 문제를 해결하는 것은 조금 어려웠다. 아마 자료구조를 활용하는데 익숙치 않아서 그런 것 같다.

이 활용 방법을 잊지말고 다음에 꼭 써먹자

💡 기억할 것 💡 

1. 리스트의 insert, delete, remove의 시간복잡도는 O(N)이다.
   리스트를 다루는 문제에서 시간초과가 난다면 이 부분을 확인해보자.
2. 리스트의 원소 삽입/삭제는 스택큐를 적절히 사용하면 처리 시간을 줄일 수도 있다.
   어느 문제든 자료구조를 잘 활용해보자.
3. append()는 리스트에 object를 추가하는 것
   extend()는 리스트에 객체(리스트, 튜플, 딕셔너리)의 element를 리스트에 appending 시키는 것
   헷갈리지 않고 사용하기!

x = [1,2,3]
x.append([4, 5])
print(x)
>>> [1, 2, 3, [4, 5]]
-----------------------
x.extend([4, 5])
print(x)
>>>[1, 2, 3, 4, 5]