백준_1406 (에디터 커서_스택_스택의 시간복잡도)

• 링크 : https://www.acmicpc.net/problem/1406

주의사항 - 스택의 시간복잡도

• 분명 쉬운 문제인데, 정답률이 낮아서 보니 다들 시간초과가 뜨는 모양이더라
  • 이를 주의하며 문제를 풀어보자..!
    

---

메모

• 앞뒤로 추가하고 하는거 보니 deque쓰는게 나을듯

• 주의사항은 "P $"할 때, 커서의 왼쪽 =/= 큐의 맨왼쪽 주의해라

• 커서는 초기에 맨 오른쪽에 있는듯

---

실행 프로세스 보기 위한 코드 - sys했는데도 시간초과

• 맨 앞에 커서가 위치해야 하므로, 스택의 0번째에 빈 숫자를 넣어줌
• 커서는 마지막 위치에 존재
• 각 입력키 별 기능을 추가해주는데, 커서가 범위를 벗어나면 안됨!!!

arr = list(input())
end = int(input())

arr.insert(0,'0') # (중요) 맨 왼쪽 커서의 자리 추가

cusor = len(arr)  # (중요) cursor는 index값이고, 초기에 맨 끝에 있어야함!!!

for _ in range(end):
    print(*arr)
    print("cusor = ", cusor)
    comm = input()
    
    if comm[0] == 'L' and cusor > 1:        # 맨앞에 있으면 이동 불가
        cusor -= 1
    elif comm[0] == 'D' and cusor < end-1:  # 맨 뒤에 있으면 이동 불가
        cusor += 1
    elif comm[0] == 'B':
        if cusor - 1 <= 0:
            continue
        arr.pop(cusor-1)
        cusor -= 1
    elif comm[0] == 'P':
        arr.insert(cusor, comm[2])
        cusor += 1
        
print(''.join(arr[1:]))

---

(중요) Stack의 pop과 append 시간복잡도

• 리스트의 길이가 N일 때,
  - list.pop(i)와 list.insert(i)의 시간복잡도는 O(N)이다

• 시간복잡도 O(1)로 줄이기 위해서
  - list.pop()과 list.append(i)를 사용해야 한다.

이런식으로 해봤는데 여전히 시간초과가 뜬다..!

arr = list(input())
end = int(input())

arr.insert(0,'0') # (중요) 맨 왼쪽 커서의 자리 추가

cusor = len(arr)  # (중요) cursor는 index값이고, 초기에 맨 끝에 있어야함!!!

for _ in range(end):
    comm = input()
    
    if comm[0] == 'L' and cusor > 1:        # 맨앞에 있으면 이동 불가
        cusor -= 1
    elif comm[0] == 'D' and cusor < end-1:  # 맨 뒤에 있으면 이동 불가
        cusor += 1
    elif comm[0] == 'B':
        if cusor - 1 <= 0:
            continue
        tmp_l = arr[:cusor]
        tmp_r = arr[cusor:]
        tmp_l.pop()
        arr = tmp_l + tmp_r
        cusor -= 1
    elif comm[0] == 'P':
        tmp_l = arr[:cusor]
        tmp_r = arr[cusor:]
        tmp_l.append(comm[2])
        arr = tmp_l + tmp_r
        cusor += 1
        
print(''.join(arr[1:]))

---

결코 간단무식한 아이디어로 푸는게 아니었다..!

• 참고 링크 : https://bnzn2426.tistory.com/112
• 다들 나처럼 pop(i)이랑 insert(i)를 썼었는데, 시간복잡도 때문에 틀렸던 것 같다.
• 그리고 문자열 최대 길이(10만)보다 명령어 입력 횟수(50만)가 훨씬 많아,
  - 데이터를 넣었다 뺐다 넣었다 뺐다를 반복할 수 있겠다고 하였다.
  • 따라서, 속도 문제가 아닌, 연산 횟수를 줄여야 한다
• 해결방법
  - 두 개의 스택을 사용하여, pop()과 append()만 사용하도록 하였다.
  
  

''' 블로그 아이디어 인용한 풀이 (스택 2개) '''
import sys

left = list(sys.stdin.readline().strip())  # .strip()를 해줘야한다.... 이거안하니까 계속 틀림
right = []
end = int(sys.stdin.readline())


for _ in range(end):
    comm = sys.stdin.readline()
    
    # 왼쪽 스택에 데이터 있으면 맨 끝 데이터를 오른쪽으로 이동
    if comm[0] == 'L':
        if left:  right.append(left.pop())
    
    # 오른쪽 스택에 데이터 있으면 맨 앞 데이터를 왼쪽으로 이동 (오른쪽은 거꾸로 생각!)
    elif comm[0] == 'D':
        if right: left.append(right.pop())
    
    # 커서 왼쪽에 데이터 있으면 pop() = 데이터 삭제
    elif comm[0] == 'B':
        if left: left.pop()
    
    # 커서 왼쪽에 데이터 추가 = 왼쪽 스택에 append()
    elif comm[0] == 'P':
        left.append(comm[2])

print(''.join(left+list(reversed(right))))