쌓거나 줄 세우거나! 스택과 큐

• 스택과 큐의 차이를 꺼내는 순서로 설명한다.
• 파이썬에서 큐를 만들 때 deque 를 쓰는 이유를 안다.
• 스택으로 짝을 맞추고, 식을 계산한다.
• 아직 답을 못 찾은 것을 쌓아두는 스택 활용을 익힌다.

비유로 이해하기 — 쌓아 올린 접시

접시를 쌓을 때는 위에 올리고, 뺄 때도 위에서 뺀다냥. 맨 아래 접시를 쓰려면 위를 다 치워야 한다냥.

• 넣기 — append — 접시를 위에 올린다
• 꺼내기 — pop — 위에서 뺀다
• 보기만 — st[-1] — 맨 위를 본다

빈 스택에서 pop 을 하면 IndexError 로 터진다냥.

꺼내기 전에 항상 비었는지 확인하자냥.

if st:
    x = st.pop()

오늘 괄호 검사 문제에서 이걸 빼먹으면 바로 에러가 난다냥.

pop(0) 은 느리다냥. 이게 오늘 꼭 기억할 부분이라냥.

맨 앞을 빼면 뒤에 있는 원소가 전부 한 칸씩 앞으로 당겨진다냥. 원소가 n개면 한 번 꺼낼 때마다 n번 옮기는 셈이라냥.

pop() (맨 뒤)은 당길 게 없어서 빠르다냥. 앞에서 빼는 것만 느리다냥.

얼마나 차이 나는지 오늘 4번 문제에서 직접 확인할 수 있다냥. 사람 4000명을 4000번째마다 빼는 문제인데, 채점기에서 재보면 이렇다냥.

• deque.rotate() — 약 0.03초
• deque.popleft() — 약 1.6초
• list.pop(0) — 시간 초과

같은 알고리즘인데 자료구조 하나로 통과와 실패가 갈린다냥.

개수만 세면 안 된다냥.

print('YES' if s.count('(') == s.count(')') else 'NO')   # 틀렸다냥!

)( 는 개수가 똑같이 하나씩이지만 올바르지 않다냥. 순서가 틀렸기 때문이라냥. 개수 세기로는 순서를 볼 수 없다냥.

괄호가 (), [], {} 세 종류면 스택에 종류까지 담아두고 꺼낼 때 대조하면 된다냥.

pair = {')': '(', ']': '[', '}': '{'}

if not st or st[-1] != pair[ch]:
    ok = False

이렇게 해야 ([)] 처럼 엇갈린 것을 잡아낸다냥. 종류를 안 보면 이게 통과해버린다냥.

빼기에서 순서가 뒤집히기 쉽다냥.

스택에서 먼저 꺼낸 것이 오른쪽 피연산자라냥. 10 3 - 는 10 - 3 이니 7 이라냥.

a = st.pop()      # 이러면 a 가 3 이 된다냥
b = st.pop()
st.append(a - b)  # 3 - 10 = -7  틀렸다냥!

더하기와 곱하기는 순서를 바꿔도 답이 같아서 빼기에서만 티가 난다냥. 그래서 더 못 찾는다냥.

그냥 오른쪽으로 하나씩 훑으면 되지 않냥? 되긴 된다냥. 느려서 문제라냥.

수가 n개면 최악의 경우 n × n 번 비교한다냥. n 이 12000만 돼도 시간 초과가 난다냥. 오늘 5번 문제의 숨겨진 테스트가 정확히 그거라냥.

비유로 이해하기 — 대기 명단

스택에 쌓인 건 "내 오큰수 아직 못 찾았어요" 하고 기다리는 번호표라냥.

새 수가 나타나면 기다리던 사람 중 그 수보다 작은 사람들은 전부 답을 찾은 것이라냥. 한꺼번에 처리하고 명단에서 지운다냥.

각 번호표는 한 번 쌓이고 한 번 지워질 뿐이라 전체가 빠르다냥.

while 안에 pop 이 있어서 이중 반복문처럼 보이지만 느리지 않다냥.

각 원소는 평생 한 번 쌓이고 한 번 꺼내진다냥. 그래서 전체 작업량이 n 에 비례한다냥. 겉모습이 아니라 총 몇 번 꺼내지냐로 세는 게 요령이라냥.