📍문제

[BOJ] 1406번: 에디터

📍첫번째 풀이

• 문자열을 리스트로 변환하고 리스트에 사용되는 메서드로 구현했다.
• cursor라는 변수를 사용해 커서의 위치를 나타내줬다.

💻나의 코드(오답)

import sys
input = sys.stdin.readline

string = list(input().strip())

commands = []
for _ in range(int(input())):
    commands.append(input().split())

cursor = len(string)
print(cursor)

for command in commands:
    if command[0] == 'L':
        if cursor == 0:
            pass
        else:
            cursor -= 1
    elif command[0] == 'D':
        if cursor == len(string):
            pass
        else:
            cursor += 1
    elif command[0] == 'B':
        if cursor == 0:
            pass
        else:
            string.remove(string[cursor-1])
    elif command[0] == 'P':
        string.insert(cursor, command[1])
        cursor += 1

print(''.join(string))

근데 이러면 일단 예제3에서 인덱스 에러가 뜨고, 구글링한 결과 이렇게 하나의 리스트로 사용하여 계산할 경우 시간초과가 뜬다는 사실을 발견..!

찾아보니 insert()를 사용할 경우 시간복잡도가 O(N)이기 때문에 시간초과가 나는 것 같았다.
그래서 많은 분들이 스택을 두개 사용해 커서의 위치를 기준으로 왼쪽, 오른쪽 부분으로 나누어 풀이를 했다는 사실을 알게되어 나도 그렇게 풀어보기로 하였다.

📍두번째 풀이(시간복잡도 반영)

pop()과 append()의 시간복잡도가 O(1)이기 때문에 이 둘만 이용해주기로 한다.

• 커서의 위치를 기준으로 stack_l과 stack_r을 나눈다. 문제에서 처음에 커서는 맨 뒤에 있다고 했으므로, 초기의 stack_r은 빈 리스트로 선언해준다.
• append를 이용해서 데이터를 추가해줬기 때문에 데이터가 뒤로 추가된다. 따라서 stack_r은 연산이 끝난 후 reverse()를 이용해서 뒤집어준다.

💻나의 코드(맞았습니다!!)

import sys
input = sys.stdin.readline

stack_l = list(input().strip())
stack_r = []

commands = []
for _ in range(int(input())):
    commands.append(input().split())

for command in commands:
    if command[0] == 'P':
        stack_l.append(command[1]) # 커서 왼쪽에 데이터 추가
    elif command[0] == 'L': 
        if stack_l: # 커서가 맨 앞이 아니라면
            stack_r.append(stack_l.pop()) 
    elif command[0] == 'D': 
        if stack_r: # 커서가 맨 오른쪽이 아닐 경우
            stack_l.append(stack_r.pop())
    elif command[0] == 'B':
        if stack_l:
            stack_l.pop()

stack_r.reverse()
print(''.join(stack_l+stack_r))

이렇게 하면 통과!

근데 소름 돋는 점

이게뭥미
C++로 풀었던 나
3년전에..
아마 저때 자료구조 수업 들었어서 풀었었나보다..