(Python) 백준 5397번 : 키로거

출처 : https://www.acmicpc.net/problem/5397

5397번: 키로거

---

 

(Python) 백준 5397번 : 키로거¶

출처 : https://www.acmicpc.net/problem/5397

---

문제 해결에 대한 생각¶

• 리스트를 이용해서 배열 하나를 만든 뒤, 커서 위치에 대한 정보를 따로 변수에 저장해서 배열의 중간에 삽입과 제거를 하게 될 경우 시간초과 발생

• deque객체는 append, appendleft, pop, popleft를 통해서 배열을 수정 할 경우 O(1)의 시간 복잡도를 갖기 때문에 속도가 빠르지만, 배열의 중간위치를 수정하게 되는 경우엔 속도가 느림.

• 따라서 양 방향에 대해서 수정이 빠른 deque 객체를 사용하되, 하나의 배열이 아닌 두개의 배열을 두고 구현하는 것이 좋을 것 같다.

• deque 객체
  • front (deque 객체) : 커서(Cursor) 앞부분에 존재하는 문자열
  • back (deque 객체) : 커서(Cursor) 뒷부분에 존재하는 문자열

---

front 배열과 back 배열이 어떤 규칙을 갖고 쌓이는지 확인해보자¶

In [1]:

from collections import deque

In [2]:

## front, back 이름을 갖는 deque객체 만들기
front = deque()
back = deque()

for item in input():
    ## '<' 입력 받을 경우
    ## front가 비어있다면 아무일도 일어나지 않는다.
    ## 그렇지 않다면 front[-1]값을 back[0]에 추가한다.
    if item == '<':
        if front:
            back.appendleft(front.pop())
    ## '>' 입력 받을 경우
    ## back이 비어있다면 아무일도 일어나지 않는다.
    ## 그렇지 않다면 back[0]값을 front[-1]에 추가한다.
    elif item == '>':
        if back:
            front.append(back.popleft())
    ## '-'를 입력 받을 경우
    ## front가 비어있지 않을 경우, front[-1]을 제거한다.
    elif item == '-':
        if front:
            front.pop()
    ## 그 외, 문자를 입력받는 경우
    ## front[-1]에 추가
    else:
        front.append(item)
    
    ## 이해를 돕기 위해 매 시행에서 front와 back이 어떻게 쌓이는지 보자.
    print("입력:",item)
    print("front:", front)
    print("back:", back)
    print()

<<BP<A>>Cd-
입력: <
front: deque([])
back: deque([])

입력: <
front: deque([])
back: deque([])

입력: B
front: deque(['B'])
back: deque([])

입력: P
front: deque(['B', 'P'])
back: deque([])

입력: <
front: deque(['B'])
back: deque(['P'])

입력: A
front: deque(['B', 'A'])
back: deque(['P'])

입력: >
front: deque(['B', 'A', 'P'])
back: deque([])

입력: >
front: deque(['B', 'A', 'P'])
back: deque([])

입력: C
front: deque(['B', 'A', 'P', 'C'])
back: deque([])

입력: d
front: deque(['B', 'A', 'P', 'C', 'd'])
back: deque([])

입력: -
front: deque(['B', 'A', 'P', 'C'])
back: deque([])

최종 code¶

In [3]:

from collections import deque

for _ in range(int(input())): ## 테스트 케이스
    ## front, back 이름을 갖는 deque객체 만들기
    front = deque()
    back = deque()

    for item in input():
        ## '<' 입력 받을 경우
        ## front가 비어있다면 아무일도 일어나지 않는다.
        ## 그렇지 않다면 front[-1]값을 back[0]에 추가한다.
        if item == '<':
            if front:
                back.appendleft(front.pop())
        ## '>' 입력 받을 경우
        ## back이 비어있다면 아무일도 일어나지 않는다.
        ## 그렇지 않다면 back[0]값을 front[-1]에 추가한다.
        elif item == '>':
            if back:
                front.append(back.popleft())
        ## '-'를 입력 받을 경우
        ## front가 비어있지 않을 경우, front[-1]을 제거한다.
        elif item == '-':
            if front:
                front.pop()
        ## 그 외, 문자를 입력받는 경우
        ## front[-1]에 추가
        else:
            front.append(item)
    ## front와 back 배열 합치기
    front.extend(back)
    ## print
    print(''.join(front))

2
<<BP<A>>Cd-
BAPC
ThIsIsS3Cr3t
ThIsIsS3Cr3t

테스트 케이스 수 : 2

입력 : <<BP>Cd
결과 : BAPC

입력 : ThIsIsS3Cr3t
결과 : ThIsIsS3Cr3t