[백준] 5397번 : 키로거

유형 : 스택, 구현, 그리디

[예제]

2
<<BP<A>>Cd-
ThIsIsS3Cr3t

[출력]

BAPC
ThIsIsS3Cr3t

---

1. 핵심 풀이 아이디어

1) 문자열 크기가 최대 1,000,000이므로 단순히 문제에서 요구한 대로 구현하게 되면 해결할 수 없다.

→ 스택을 활용하여 선형시간 문제를 해결할 수 있는 알고리즘을 설계 필요

 

2) 해결 방향

[          왼쪽 스택          | 커서 |           왼쪽 스택           ]

① 스택 2개를 만들어 스택 사이 중간지점을 커서로 간주

② 문자 입력 : (커서 기준)왼쪽 스택에 원소 삽입

③ - 입력 : 왼쪽 스택에서 원소 삭제

④ < 입력 : 왼쪽 스택에서 오른쪽 스택으로 원소 이동

⑤ > 입력 : 오른쪽 스택에서 왼쪽 스택으로 원소 이동

** 오른쪽 스택의 경우, 마지막 출력할 때 스택을 뒤집어서 출력해야 함!

 

강의에서 나온 예시

강의에서 설명한 핵심 아이디어를 본 예시에 적용해서 해석(?)했다.

 

2. 풀이

밑에는 내 풀이(틀림)인데...다시 풀어봐야 한다..

## 백준 5397
L = int(input())

for _ in range(L):
    text = input()
    #text = [(i, idx) for idx,i in enumerate(text)]
    cursor = 0 # 커서 위치
    temp = []
    count = 0

    for j in range(len(text)):
        if text[j] in ('<','>','-'):
            k = j
            c1 = 0
            c2 = 0
            c3 = 0

            if count == 0: # 앞에 텍스트 없는 경우
                continue

            while True:
                if text[k] == '<':
                    c1 += 1
                elif text[k] == '>':
                    c2 += 1
                elif text[k] == '-':
                    print(temp)
                    print(count-c1-c2-1)
                    temp.pop(count-c1+c2-1)
                    c3 += 1
                else:
                    break
                k += 1

            cursor = cursor - c1 + c2 # 커서 위치 조정

        else:
            temp.append(text[j])
            cursor += 1
            count += 1

    for i in range(len(temp)):
        print(temp[i], end='')

 

풀이

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))

 

'출력 초과'가 나와서 코드를 조금 수정하였다.
(출력 부분에서 왼쪽 스택과 오른쪽 스택을 합치는 부분을 print() 안에 들어가게끔)

print(''.join(left_stack) + ''.join(reversed(right_stack)))

 

백준 링크 https://www.acmicpc.net/problem/5397

5397번: 키로거

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online