[Algorithm] 5397. 키로거

5397. 키로거

5397번 문제 보기

기본적인 방향부터 세부적인 조건 처리까지 어떻게 풀이해야 할 지 고민이 많이 되었던 문제다...
실버 2인데 코테 준비 빡세게 해야한다는 경각심을 일깨워준 문제!!

접근 방식

바킹독의 실전 알고리즘 문제 리스트에서 연결리스트 기본 문제를 복습하던 중,
"연결 리스트 챕터이니 당연히 연결 리스트로 접근해야겠지?"라고 생각했다.

문제에 대해 고민을 더 하다 보니, 화살표 키를 의미하는 < ,> 와 백스페이스를 의미하는 -의 특징이 후입선출(LIFO)의 성격을 가지는 stack을 사용해 풀이해야한다는 힌트를 준 것 같아, 접근 방식을 변경하였다.

1️⃣
스택으로 관리할 변수를 2개 두었다.
left_stack과 right_stack.

import sys
input = sys.stdin.readline

n = int(input())

for _ in range(n):
  left_stack = []
  right_stack = []
  cmd = input().rstrip()
  
  # ...

2️⃣
입력 값 <, >, -, 문자에 따라 분기 처리를 해준다.

• <의 경우 : left_stack의 empty 여부 확인 후 right_stack에 왼쪽 스택의 마지막 값을 보냄
• >의 경우 : right_stack의 empty 여부 확인 후 left_stack에 오른쪽 스택의 마지막 값을 보냄
• -의 경우 : left_stack의 empty 여부 확인 후 왼쪽 스택의 가장 마지막 값을 pop()
• 문자의 경우 : left_stack에 append()

import sys
input = sys.stdin.readline

n = int(input())

for _ in range(n):
  left_stack = []
  right_stack = []
  cmd = input().rstrip()

  for i in cmd:
    if i == '<':
      if left_stack:
        right_stack.append(left_stack.pop())
    elif i == '>':
      if right_stack:
        left_stack.append(right_stack.pop())
    elif i == '-':
      if left_stack:
        left_stack.pop()
    else:
      left_stack.append(i)

3️⃣
스택의 특성 상, 오른쪽 스택(right_stack)에는 반대로 정렬되므로,
reversed(right_stack)의 값을 left_stack에 추가한다.

• append() : list.append(x)는 리스트 끝에 x 1개를 그대로 추가
• extend() : list.extend(iterable)는 리스트 끝에 가장 바깥쪽 iterable의 모든 항목을 추가

  left_stack.extend(reversed(right_stack))

4️⃣
정답 값이 들어있는 left_stack를 출력한다.

• ''.join(list)
  • ''.join(list)를 이용하면 매개변수로 들어온 ['a', 'b', 'c'] 형식의 리스트를 abc의 문자열로 합쳐서 반환

    print(''.join(left_stack))

최종 코드

import sys
input = sys.stdin.readline

n = int(input())

for _ in range(n):
  left_stack = []
  right_stack = []
  cmd = input().rstrip()

  for i in cmd:
    if i == '<':
      if left_stack:
        right_stack.append(left_stack.pop())
    elif i == '>':
      if right_stack:
        left_stack.append(right_stack.pop())
    elif i == '-':
      if left_stack:
        left_stack.pop()
    else:
      left_stack.append(i)
  left_stack.extend(reversed(right_stack))

  print(''.join(left_stack))

배운 점

• input = sys.stdin.readline을 사용했을 때 오답이 나오는 문제의 해결법은! input().rstrip()을 해줄 것.
  • 이유 : sys.stdin.readline의 경우 빠른 입출력을 지원한다는 장점이 있으나, \n 줄바꿈 기호를 입력 값에 포함시키기에, 공백 제거가 필요
• append() : list.append(x)는 리스트 끝에 x 1개를 그대로 추가
• extend() : list.extend(iterable)는 리스트 끝에 가장 바깥쪽 iterable의 모든 항목을 추가

느낀 점

• 문제의 챕터와 레벨을 가급적 보지 않고 풀이하는 연습을 하자!
• 이제 코테 준비 쉬지 말기... 제발!!!