[백준 5397번] 키로거

📌 문제

👊 백준 5397번 - 키로거

---

📌 개념

stack list

• stack은 가장 나중에 들어온 자료가 가장 먼저 처리되는 LIFO 자료구조이다.
• 파이썬에서는 list를 사용하므로 stack 자료구조를 따로 제공하지 않는다.

---

❎ 첫번째 시도 (시간초과)

❌ 시간초과로 통과되지 못한 코드이다 😥

• 

• 1개의 스택을 사용하여 현재의 커서(curr_index)를 통해 삽입, 삭제, 이동을 구현하였다.
• 커서가 문자열 중간에 있는 경우 모든 문자를 오른쪽으로 1칸씩 이동시키기 위해 insert(index, 문자)를 이용하였다. insert(index, 요소)는 리스트의 특정 index에 요소 하나를 추가한다.

Code

n = int(input())

for i in range(n):
    stack = []
    curr_index = 0
    write = input()
    for ch in write:
        if ch == "<":
            if curr_index != 0:
                curr_index -= 1
        elif ch == ">":
            if curr_index != len(stack) and len(stack) != 0:
                curr_index += 1
        elif ch == "-":
            if len(stack) != 0 and curr_index != 0:
                stack.pop(curr_index - 1)
                curr_index -= 1
        else:
            stack.insert(curr_index, ch)
            curr_index += 1
    print("".join(stack))

+ 내 생각

• 입출력은 제대로 되는 것 같은데...
• stack.insert(curr_index, ch)와 stack.pop(index) 때문에 시간초과가 발생한 게 아닐까 하는 생각이 든다.
• 참고로 list.insert(index, 요소)와 list.pop(index)의 $Big-O$ 시간복잡도는 $O(N)$이라고 한다.

---

✅ 문제 해결

• 현재 커서를 다음과 같이 2가지 스택의 중간 지점으로 설정하였다. 즉 현재 커서는 left_stack의 끝이다.
• -의 경우 left_stack이 비어 있지 않은 경우 left_stack.pop()을 통해 현재 커서의 왼쪽의 값 1개를 삭제한다.
• <의 커서를 왼쪽으로 한 칸 이동한다. 즉, 반대로 생각하면 커서 왼쪽의 값 1개를 오른쪽 스택으로 넘기면 된다.
• >의 경우도 마찬가지로 커서 오른쪽 값 1개를 왼쪽 스택으로 넘기면 된다.
• 추가할 때는 왼쪽 스택에 값을 추가한다.

Code

test_case = int(input())

for _ in range(test_case):
    left_stack = []
    right_stack = []
    data = input()
    for i in data:
        if i == "-":
            if left_stack:
                left_stack.pop()
        elif i == "<":
            if left_stack:
                right_stack.append(left_stack.pop())
        elif i == ">":
            if right_stack:
                left_stack.append(right_stack.pop())
        else:
            left_stack.append(i)
    left_stack.extend(reversed(right_stack))
    print("".join(left_stack))