PostsSeriesLabsAlgo

자료구조

스택

왜 Ctrl+Z 는 방금 한 것부터 되돌릴까

문서에 글자 굵게 → 그림 넣기 → 색 바꾸기 를 차례로 합니다. 그리고 되돌리기를 두 번 누릅니다.
문서에 무엇이 남을까요? 먼저 골라 보세요.

한 일 0 · 되돌린 횟수 0

내 예상 · 실제 → 달랐어요

되돌릴 때 나간 순서는 였습니다. 가장 먼저 한 일이 끝까지 남았습니다.

글자 굵게 → 그림 넣기 → 색 바꾸기한 순서입니다. 되돌릴 때는 거꾸로 된 순서로 나갔습니다.

나중에 넣은 것이 먼저 나오는 더미 = 스택

왜 맨 위만 꺼낼 수 있을까

  • 열린 쪽이 한 곳 — 넣을 때도 꺼낼 때도 맨 위다
  • 가운데는 못 꺼낸다 — 위에서 가운데 일을 눌렀을 때 안 된다고 한 이유다
  • 그래서 — 가장 나중에 들어온 것이 가장 먼저 나온다

괄호도 같습니다. ( [ { } ] ) 에서 안쪽 { } 가 가장 나중에 열려서 가장 먼저 닫힙니다.

코드는 쌓고 걷는 두 줄이 전부다

문자열을 고르고 다음을 눌러 한 줄씩 넘기세요. 여는 괄호는 쌓이고 닫는 괄호는 맨 위와 짝을 맞춘 뒤 걷힙니다.

다음을 눌러 한 줄씩 넘겨 보세요

깊이 = 0

is_balanced.py
  1. 1def is_balanced(s):
  2. 2 pairs = {")": "(", "]": "[", "}": "{"}
  3. 3 stack = []
  4. 4 for c in s:
  5. 5 if c in "([{":
  6. 6 stack.append(c)
  7. 7 elif c in pairs:
  8. 8 if not stack or stack[-1] != pairs[c]:
  9. 9 return False
  10. 10 stack.pop()
  11. 11 return not stack
0 / 28
  • stack.append(c) — 여는 괄호를 맨 위에 올린다
  • stack[-1] — 맨 위를 본다. 꺼내지 않고 보기만 한다
  • stack.pop() — 맨 위를 꺼낸다. 짝이 맞을 때만 한다
  • return not stack — 다 읽고 나서 스택이 비어 있어야 짝이 맞다

파이썬에는 스택이 따로 없습니다. 리스트의 맨 뒤에서만 넣고 빼면 그게 스택입니다.

문자열 ( ( ) 을 끝까지 읽었습니다. 스택에는 무엇이 남을까요?

비었는데 꺼내면 터진다

  • 빈 스택에서 pop() — ) 하나만 있는 문자열에서 IndexError 가 난다. 먼저 not stack 으로 비었는지 본다
  • stack[-1] 도 같다 — 비었으면 IndexError 다. 코드 8번 줄이 not stack or … 로 먼저 거르는 이유다
  • 다 읽었는데 남았다 — ( ( ) 는 닫는 괄호가 모자란 것이다. 마지막 줄을 return True 로 쓰면 틀린 문자열에 True 라고 답한다
  • pop(0) — 맨 앞을 꺼내면 나머지를 한 칸씩 당긴다. 10만 개를 이렇게 다 꺼내면 칸을 약 50억 번 옮긴다. 꺼낼 때는 pop()

문제에서 이 말이 보이면

괄호되돌리기 · 가장 최근같은 쌍이 안쪽부터 끝난다

다음 장에서는 먼저 온 것부터 나가는 큐와 덱을 봅니다.