문제를 푸는 기준

최근 상태로 되돌아가면 스택, 대기 순서대로 처리하면 큐를 떠올립니다. 큐는 head 인덱스를 두어 앞 원소 삭제 비용을 피합니다.

핵심 개념

대표 문제

괄호 문자열 검사

소괄호·대괄호·중괄호 문자열 text가 올바르게 열리고 닫히면 true, 아니면 false를 반환하세요.

함수 시그니처: solution(text)

제한사항

• text의 길이는 0 이상 200,000 이하입니다.
• text에는 괄호 문자만 들어 있습니다.

입출력 예

풀이 설계

1. 여는 괄호는 스택에 넣습니다.
2. 닫는 괄호에서 스택 꼭대기의 짝을 확인합니다.
3. 모든 문자 뒤 스택이 비었는지 반환합니다.

JavaScript 풀이

function solution(text) {
  const stack = [];
  const opening = new Set(['(', '[', '{']);
  const pair = { ')': '(', ']': '[', '}': '{' };
  for (const char of text) {
    if (opening.has(char)) stack.push(char);
    else if (stack.pop() !== pair[char]) return false;
  }
  return stack.length === 0;
}

복잡도

• 시간복잡도: O(n)
• 공간복잡도: O(n)
• 핵심 패턴: 여는 기호를 쌓고 닫는 기호에서 짝 확인
• 경계 사례: 닫는 괄호가 먼저 나오거나 여는 괄호가 남으면 false

연습 문제

1. 문자 지우기

별표마다 바로 앞 문자를 지운 결과를 반환하세요.

2. 작업 대기열

처리 시간으로 완료 순서를 반환하세요.

3. 다음 큰 값

오른쪽 첫 큰 값을 반환하세요.

자주 하는 실수

• 빈 스택에서 닫는 괄호를 처리하지 않는 실수
• 마지막 스택 길이를 확인하지 않는 실수
• 큐에서 shift를 반복하는 실수
• 인덱스가 필요한 문제에서 값만 저장하는 실수

핵심 정리

• 함수 시그니처와 반환 자료형을 먼저 확정합니다.
• 제한사항으로 가능한 시간복잡도를 판단합니다.
• 예시와 경계 사례를 손으로 추적한 뒤 구현합니다.
• 완성한 solution 함수가 입력을 불필요하게 바꾸지 않는지도 확인합니다.

확인 문제

참고 자료

• Princeton Algorithms 4e - Stacks and Queues 
• MDN Array 
• 프로그래머스 코딩테스트 고득점 Kit