자료구조O(n)

올바른 괄호 판별

여는 괄호는 쌓고, 닫는 괄호에서 짝을 맞춰요. 스택 한 번이면 끝나요.

이럴 때 써요

괄호가 올바르게 열리고 닫혔는지 확인할 때
(), [], {} 처럼 여러 종류의 괄호가 섞여 짝이 맞는지 볼 때
가장 최근에 연 것부터 닫아야 하는 후입선출 구조가 보일 때
후위 표기법 계산처럼 마지막에 넣은 값을 먼저 꺼내 처리하는 문제일 때

개념

괄호는 가장 최근에 연 것부터 닫아야 올바른 괄호예요. 이 '최근 것 먼저'가 바로 스택이에요. 여는 괄호를 만나면 스택에 push, 닫는 괄호를 만나면 스택 맨 위와 짝인지 확인하고 pop 해요. 문자열을 한 번만 훑으니 O(n)이에요.다 훑고 나서 스택이 비어 있어야 올바른 괄호예요. 스택에 뭔가 남았다면 닫지 않은 괄호가 있다는 뜻이거든요. ()[]{} 처럼 종류가 여럿이면 ) ↔ (, ] ↔ [, } ↔ { 짝을 표로 들고 다니면서 맞춰요.

"([])" 는 올바른 괄호일까 — 스택으로 확인해요
s = ([])  ,  스택은 비어서 시작해요
'(' :  여는 괄호  →  push      스택 [ ( ]
'[' :  여는 괄호  →  push      스택 [ ( [ ]
']' :  맨 위 '[' 와 짝  →  pop  스택 [ ( ]
')' :  맨 위 '(' 와 짝  →  pop  스택 [ ]
끝났는데 스택이 비어 있음  →  올바른 괄호 (true)

"(]" 는 올바르지 않아요 — 짝이 안 맞는 순간 멈춰요
s = (]  ,  스택은 비어서 시작해요
'(' :  여는 괄호  →  push      스택 [ ( ]
']' :  맨 위는 '(' 인데 ']' 의 짝은 '[' 예요
       짝이 안 맞음  →  바로 false

이 스택 뼈대는 그대로 확장돼요. 후위 표기법 계산(eval-postfix)도 숫자는 스택에 쌓고 연산자를 만나면 위의 두 값을 꺼내 계산해 다시 넣는, 똑같은 후입선출 패턴이에요.

패턴 코드

스택으로 올바른 괄호 판별닫는 괄호의 짝을 pairs 표에 담아 두고, 스택 맨 위와 비교해요.

javascript
Copy code
function isValid(s) {
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const ch of s) {
    if (ch === "(" || ch === "[" || ch === "{") {
      stack.push(ch);
    } else {
      // 빈 스택에서 꺼내면 undefined 라 짝이 안 맞아 false 가 돼요
      if (stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.length === 0;
}

이 유형으로 풀어보기

← 소인수분해 다음 큰 수 — 모노토닉 스택 →