코딩테스트 연습장

식당 주방에 쌓인 접시 더미를 떠올려 보세요. 씻은 접시는 더미 맨 위에 올리고, 쓸 때도 맨 위에서 한 장씩 가져갑니다. 아래에 깔린 접시를 꺼내려면 위에 쌓인 것을 전부 치워야 하므로, 실제로 오가는 것은 항상 맨 위 한 장뿐입니다. 그래서 가장 나중에 올린 접시가 가장 먼저 나갑니다.

스택은 한쪽 끝으로만 넣고 빼는 자료구조이며, 마지막에 넣은 것이 가장 먼저 나옵니다 (LIFO, Last-In First-Out, 후입선출).

올리기: 접시 더미 ← A, B, C 순서로 올림 → 위에서부터 C, B, A
꺼내기: 맨 위 C가 먼저 → 그다음 B → 마지막에 A
중간의 B만 꺼내는 일은 없습니다 — 스택이 아니게 됩니다

괄호 문자열 ([])가 올바른지 손으로 확인해 봅니다. 여는 괄호는 더미에 올리고, 닫는 괄호를 만나면 맨 위를 꺼내 짝이 맞는지 봅니다.

읽은 글자	동작	스택 상태 (왼쪽이 아래)	판정
`(`	올리기	`[ ( ]`	계속
`[`	올리기	`[ (, [ ]`	계속
`]`	꺼내니 `[`	`[ ( ]`	짝 맞음
`)`	꺼내니 `(`	`[ ]`	짝 맞음
끝	—	비어 있음	올바름

마지막에 스택이 비어 있어야 올바른 문자열입니다. 만약 입력이 (((였다면 한 번도 꺼내지 않아 끝에 [ (, (, ( ]가 남고, 이때는 여는 괄호가 초과라서 올바르지 않습니다. 끝난 뒤 비었는지 확인하는 것까지가 검사입니다.

TypeScript에서는 배열이 곧 스택입니다. push/pop이 배열 끝에서 일어나므로 별도 구현이 필요 없고, 두 연산 모두 O(1)입니다.

빈 배열로 스택을 만듭니다.

const stack: string[] = [];

넣을 때는 push, 꺼낼 때는 pop, 보기만 할 때는 마지막 인덱스를 씁니다.

stack.push("(");                       // 맨 위에 올리기
const top = stack[stack.length - 1];   // peek — 꺼내지 않고 보기
const out = stack.pop();               // 꺼내기 (빈 배열이면 undefined)

조건에 따라 넣거나 꺼내며 순회하고, 마지막에 남은 것을 확인합니다.

for (const ch of s) {
  if (ch === "(") stack.push(ch);
  else if (stack.pop() !== "(") return false; // 짝이 안 맞음
}
return stack.length === 0; // 남으면 여는 괄호가 초과

전체 코드 — 괄호 검사, 스택의 대표 문제:

function isValid(s: string): boolean {
  // 1단계: 스택 준비
  const stack: string[] = [];
  const pair: Record<string, string> = { ")": "(", "]": "[", "}": "{" };
  // 2~3단계: 여는 괄호는 올리고, 닫는 괄호는 꺼내 짝 확인
  for (const ch of s) {
    if (ch === "(" || ch === "[" || ch === "{") stack.push(ch);
    else if (stack.pop() !== pair[ch]) return false;
  }
  return stack.length === 0;
}

"가장 최근 것부터 되짚어야 할 때" 스택을 떠올리세요.

짝 맞추기: 괄호 검사 — 여는 괄호를 push, 닫는 괄호를 만나면 pop해서 짝 확인
되돌리기: 실행 취소(undo), 브라우저 뒤로 가기
가장 가까운 이전 원소 찾기: 모노토닉 스택 — "내 왼쪽에서 나보다 큰 가장 가까운 값"류
DFS: 재귀 호출 자체가 콜 스택이며, 명시적 스택으로도 구현 가능
지문 신호: "직전", "가장 최근", "짝이 맞는", "중첩된", "취소하면 이전 상태로" — 모두 스택 신호입니다.

핵심 연산은 세 가지뿐이고 전부 O(1)입니다.

연산	의미	JS/TS
push(x)	top에 x를 올린다	`arr.push(x)`
pop()	top을 꺼낸다	`arr.pop()`
peek()	top을 꺼내지 않고 본다	`arr[arr.length - 1]`

// 모노토닉(단조) 스택 — 각 원소의 "다음으로 큰 값의 인덱스"
function nextGreater(nums: number[]): number[] {
  const answer = Array(nums.length).fill(-1);
  const stack: number[] = []; // 아직 답을 못 찾은 인덱스들 (값은 내림차순 유지)
  for (let i = 0; i < nums.length; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      answer[stack.pop()!] = i; // i가 그들의 "다음 큰 값"
    }
    stack.push(i);
  }
  return answer;
}

// 문자열 소거 — 같은 글자가 연달아 오면 지우기
function removeAdjacent(s: string): string {
  const stack: string[] = [];
  for (const ch of s) {
    if (stack[stack.length - 1] === ch) stack.pop(); // 직전 글자와 같으면 소거
    else stack.push(ch);
  }
  return stack.join(""); // 문자열 += 대신 마지막에 join
}

pop 전에 빈 스택 확인 누락 — stack.pop()은 빈 배열에서 undefined를 조용히 반환하므로 버그가 숨습니다.

if (stack.pop() !== pair[ch]) return false;                      // 잘못: 빈 스택도 통과 판정이 애매
if (!stack.length || stack.pop() !== pair[ch]) return false;     // 고침: 비었으면 즉시 실패

괄호 검사에서 순회가 끝난 뒤 stack.length === 0 확인을 잊음 — "(((" 같은 입력이 통과해 버립니다.

return true;                    // 잘못: 남은 여는 괄호를 못 잡음
return stack.length === 0;      // 고침

모노토닉 스택에 값이 아니라 인덱스를 넣어야 하는 상황에서 값을 넣음 — 답 배열을 채우려면 위치가 필요합니다.

stack.push(nums[i]);   // 잘못: 나중에 answer의 몇 번 칸을 채울지 모름
stack.push(i);         // 고침: 값은 nums[i]로 언제든 읽을 수 있음

문자열을 스택처럼 쓰며 s += ch 반복 — 문자열은 불변이라 O(N²)입니다. 배열에 모아 마지막에 join하세요.

let out = ""; for (const ch of s) out += ch;   // 잘못: 매번 새 문자열 생성
const buf: string[] = []; buf.push(ch); buf.join(""); // 고침

왜 push/pop이 O(1)인가: 배열의 끝에서만 움직이므로 다른 원소를 밀 필요가 없습니다. 반대로 앞에서 빼는 shift는 뒤 원소를 전부 당겨야 해서 O(N)이며, 그래서 스택은 배열로 만들어도 손해가 없지만 큐는 그렇지 않습니다.
모노토닉 스택이 O(N)인 이유: while 루프가 중첩되어 보이지만, 각 인덱스는 스택에 정확히 한 번 들어가고 최대 한 번 나옵니다. 전체 pop 횟수가 N을 넘지 않으므로 총합이 O(N)입니다(분할 상환 분석).
재귀와 콜 스택: 재귀 호출은 언어 런타임이 관리하는 스택에 지역 변수와 복귀 주소를 쌓는 일입니다. 깊이가 수만에 이르면 스택 오버플로가 나므로, DFS 깊이가 큰 문제는 재귀를 명시적 스택 반복문으로 바꿔 씁니다.
후위 표기식 계산: 수식 계산기 문제는 스택 두 개(값 스택, 연산자 스택)로 풉니다. 연산자 우선순위가 낮은 것이 들어오면 스택에 쌓인 높은 연산자를 먼저 처리해 내리는 식입니다.
최솟값을 O(1)로 아는 스택: 값 스택과 같은 높이로 "그 시점까지의 최솟값" 스택을 하나 더 유지하면, 언제든 최솟값을 O(1)에 조회할 수 있습니다.

위 시각화로 push/pop의 흐름을 눈에 익힌 뒤, 아래 문제를 난이도 순으로 푸세요. 괄호 검사 → 문자열 처리 → 모노토닉 스택 순으로 이어집니다.

스택

눈으로 보기

개념 이해

비유로 이해하기

문제로 확인

스택

눈으로 보기

개념 이해

비유로 이해하기

문제로 확인