처음에는 문제의 요구사항대로 그냥 구현만 해주면 된다고 생각했다. 즉, 커서라는 변수를 하나 선언하고 커서의 위치에 따라 L, D, B, P라는 명령어 각각을 올바르게 수행해주면 된다고 생각한 후 코드를 작성했다.
import sys
input = sys.stdin.readline
'''
L: 커서를 왼쪽으로 한 칸 옮긴다 / 커서가 맨 앞이면 무시한다.
D: 커서를 오른쪽으로 한 칸 옮긴다 / 커서가 문장의 맨 뒤면 무시한다.
B: 커서 왼쪽에 있는 문자를 삭제한다 / 커서가 문장의 맨 앞이면 무시된다.
P $: $ 문자를 왼쪽에 추가한다.
'''
target_string = list(input().rstrip())
n = int(input())
cursor = len(target_string)
for _ in range(n):
operation = input().rstrip()
if operation[0] == 'P':
_, input_char = operation.split(' ')
target_string.insert(cursor, input_char)
cursor += 1
elif operation == 'L' and cursor > 0:
cursor -= 1
elif operation == 'D' and cursor <= len(target_string):
cursor += 1
elif operation == 'B' and cursor > 0:
target_string.pop(cursor-1)
if cursor > 0:
cursor -= 1
print(''.join(target_string))
하지만 해당 반식은 시간초과가 발생한다. 사실 pop 연산을 맨 끝에서 수행한다면 문제가 없지만, pop 연산을 위와 같이 중간에서 사용한다면 시간이 굉장히 오래걸린다. 왜냐하면 중간에 한 값을 빼고 나머지 값은 모두 앞으로 땡겨와야 하기 때문에 최악의 경우 O(n)만큼의 시간이 소요된다. 현재 총 500,000 명령어를 입력받을 수 있고, 문자열의 길이는 최대 100,000이므로 최악의 경우 50,000,000,000번 연산을 수행해야 한다. (물론 정확히 계산하면 더 적게 걸리지만, 그만큼 많이 소요된다.)
따라서 두 번째로 생각한 방법이 커서 변수를 사용해 중간에서 pop을 사용하지 말고, 커서를 기준으로 리스트를 두 개 사용하는 방식을 떠올렸다. 예를 들어, "abcd"라는 문자열이 주어지고 커서가 b오른쪽에 있는 상태면 한 쪽에는 "ab" 다른 쪽에는 "cd"를 놓는 것이다. (단, 커서를 기준으로 오른쪽은 반대로 저장할 것이다. 스택의 특성상 반대로 저장하는 것이 편하다. 즉, 위 경우 "cd"가 아니라 "dc"로 저장한다.) 해당 코드는 아래와 같다.
import sys
input = sys.stdin.readline
left_target_string = list(input().rstrip())
right_target_string = list()
n = int(input())
for _ in range(n):
operation = input().rstrip()
if operation[0] == 'P':
_, input_char = operation.split(' ')
left_target_string.append(input_char)
elif operation == 'L' and left_target_string:
right_target_string.append(left_target_string.pop())
elif operation == 'D' and right_target_string:
left_target_string.append(right_target_string.pop())
elif operation == 'B' and left_target_string:
left_target_string.pop()
left_target_string.extend(reversed(right_target_string))
print(''.join(left_target_string))
'Algorithm > Data Structure' 카테고리의 다른 글
[백준] 10866: 덱 (python 파이썬) (2) | 2024.04.07 |
---|---|
[백준] 10845: 큐 (python 파이썬) (0) | 2024.04.06 |
[백준] 1874: 스택 수열 (python 파이썬) (0) | 2024.04.04 |
[백준] 9012: 괄호 (python 파이썬) (0) | 2024.04.04 |
[백준] 10828: 스택 (python 파이썬) (0) | 2024.04.04 |