[Python] BOJ 1406 : 에디터

요구사항

1. 시간 제한 0.3초 
   1. 1초에 약 1억번 연산을 하니 O(N)일 때, 3천만 정도 연산 
   2. 현재  O(logN)이하 복잡도를 가지는 알고리즘을 사용할 것. 
2. 메모리 제한은 5121MB 로 걱정할 프로그램을 만들 때, 크게 고려하지 않아도 된다. 
3. 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램

설계 1

1. 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치
2. 커서의 위치를 인덱스처럼 사용해서 삽입 삭제를 하자. 
3. L 일 때
   1. cursor  > 0 보다 크다면, (계속 L L L L 해서 커서가 더이상 맨앞으로 갈 수 없는 경우를 제외함)
      1. cursor -= 1
4. D 일 때
   1. cursor < len(sentence)
      1. cursor += 1
5. B 일 때
   1. sentence.pop(cursor - 1)
   2. cursor -= 1 커서의 위치도 옮겨야함
6. P 일 때
   1. sentence.insert(cursor, command[1]) 커서 위치에 문자를 넣는다.
   2. cursor += 1
7. print("".join(sentence))

구현 1

import sys
input = lambda: sys.stdin.readline().rstrip()

sentence = list(input())  # 초기 문자열을 리스트로 변환
repeat = int(input())  # 명령어 수 입력
commands = [input().split() for _ in range(repeat)]  # 명령어 입력

cursor = len(sentence)  # 커서는 처음에 문자열 끝에 위치

for command in commands:
    if command[0] == "L":  # 커서를 왼쪽으로 한 칸 이동
        if cursor > 0:
            cursor -= 1
    elif command[0] == "D":  # 커서를 오른쪽으로 한 칸 이동
        if cursor < len(sentence):
            cursor += 1
    elif command[0] == "B":  # 커서 왼쪽에 있는 문자 삭제
        if cursor > 0:
            sentence.pop(cursor - 1)
            cursor -= 1
    elif command[0] == "P":  # 커서 왼쪽에 문자를 추가
        sentence.insert(cursor, command[1])
        cursor += 1

# 리스트를 문자열로 변환하여 출력
print("".join(sentence))

시간 초과

• 커서를 기준으로 왼쪽과 오른쪽을 나누어 저장한다
• 현재 insert, pop 은 최악의 경우 O(N)의 연산이 수행된다.
• 예를 들어 현재는 맨 앞에 삽입하게 되면 모든 원소가 하나씩 뒤로 밀리게 된다. 
• 두 개의 스택을 이용해 삽입과 삭제 O(1)로 만들 수 있다. 

설계 2

• 커서를 기준으로 왼쪽과 오른쪽 리스트를 초기화한다. 
• L 일 때 만약 왼쪽 리스트 가 있다면 오른쪽에 있는 리스트를 append 한다. 
  • if left_stack: 을 하면 리스트가 비어있을 때  false이므로 if 문 아래 소스 코드를 실행하지 않는다. 
• D일 때 L의 로직에 반대로 해주면 된다. 
• B 일 때 커서 왼쪽을 삭제해야 되므로
  • pop을 해준다. 
• P일 때도 커서 왼쪽이므로 
  • left에 append(command[1])을 해준다.
• 출력은 왼쪽과 오른쪽을 더해준다. 

구현

import sys
input = lambda: sys.stdin.readline().rstrip()

# 초기 문자열을 왼쪽 스택에 저장
left_stack = list(input())
right_stack = []
repeat = int(input())

for _ in range(repeat):
    command = input().split()
    
    if command[0] == "L":  # 커서를 왼쪽으로 한 칸 이동
        if left_stack:
            right_stack.append(left_stack.pop())
    elif command[0] == "D":  # 커서를 오른쪽으로 한 칸 이동
        if right_stack:
            left_stack.append(right_stack.pop())
    elif command[0] == "B":  # 커서 왼쪽에 있는 문자 삭제
        if left_stack:
            left_stack.pop()
    elif command[0] == "P":  # 커서 왼쪽에 문자를 추가
        left_stack.append(command[1])

# 최종 출력: 왼쪽 스택 + 오른쪽 스택을 뒤집어서 출력
# print(left_stack, right_stack)
print("".join(left_stack + right_stack[::-1]))