백준 알파벳 블록 27497번

문제

백준 27497번
https://www.acmicpc.net/problem/27497

문제 이해

이 문제를 사실, 어제 밤에 풀다가 "가장 나중에 추가된 블록을 어떻게 처리하지??" 라고 생각하고 도전하다가 피곤하기 때문에 일단 냅뒀다.
그러고 다음 날(오늘! 지금! 이 순간!) 문제를 보면서 deque와 stack을 같이 사용하면 되지 않을까?!
유레카!처럼 갑자기 번뜩 떠올랐다.
스택으로 deque에 저장할 때, stack도 저장하면 가장 최근에 append 된 값을 알 수 있으니까!!!

파이썬 코드

• 1차 도전

  import sys
  from collections import deque
  N = int(sys.stdin.readline())
  stack = []
  string_block = deque()
  for _ in range(N):
      informs = list(map(str, sys.stdin.readline().split()))
      if informs[0] == '1':
          stack.append(informs[1])
          string_block.append(informs[1])
      elif informs[0] == '2':
          stack.append(informs[1])
          string_block.appendleft(informs[1])
      else:
          if stack:
              last_block = stack.pop()
              if last_block == string_block[0]:
                  string_block.popleft()
              else:
                  string_block.pop()
  if string_block:
      print("".join(string_block))
  else:
      print(0)

• 1차 결과 : 시간초과
  --> list(map(str, input().split()))으로 해서 그런가보다 하고
  sys.stdin.readline().split() 으로 했는데...
  출력초과? 도 뜨고 수정하고 내니까 틀렸다고 나오는 게 아닌가.

아무리봐도 눈을 크게 뜨고 봐도 ... 예시 출력 값과 동일하게 나오는데...

그래서 참다못해서 다른 사람들 코드를 봤는ㄴ데
진짜 나랑 똑같다? 유사했는데 뭐가 문제지? 하고 생각했는데..

--> 내가 짠 코드에는 문제가 있었다.

만약에,

• 1 "b"
• 1 "a"
• 2 "a"
  를 한다고 치자.

그럼, deque에 [ a, b, a ] 가 되고 stack은 [b,a,a]가 된다.
stack.pop()해서 나온 값을 'a'이고, 내 코드상 실행하면 그냥 같은 값인지 파악하고 넘어가기 때문에 문제가 있는 것...

내가 짠 코드에서는 그냥 마지막 값이랑 같으면 마지막 값 뽑아내고 pass
아니면, 앞에서 값 추출 후 pass 인데
if stack.pop() == deque[0]:
deque.leftpop()
else:
deque.pop()

deque[0]과 deque[-1]이 동일하게 같은 값인데,
if 문에 앞(deque[0])을 먼저 볼건지, 뒤(deque[-1])를 볼건지를 작성하는 지에 따라 답이 달라지는 것이다.

최종 코드

import sys
from collections import deque
N = int(sys.stdin.readline())
stack = []
string_block = deque()
for _ in range(N):
    informs = list(map(str, sys.stdin.readline().split()))
    if informs[0] == '1':
        stack.append("back")
        string_block.append(informs[1])
    elif informs[0] == '2':
        stack.append("front")
        string_block.appendleft(informs[1])
    else:
        if stack:
            last_block = stack.pop()
            if last_block == "front":
                string_block.popleft()
            else:
                string_block.pop()
if string_block:
    print("".join(string_block))
else:
    print(0)