[코딩테스트] 스택 문제 1. 괄호 짝 맞추기

개념 정리

프로그래밍에서 스택(Stack)은 말 그대로 데이터를 "쌓는" 자료구조 이다.

가장 나중에 넣은 데이터가 가장 먼저 나오는 구조이기 때문에, 이를 후입선출 또는 LIFO(Last In First Out)이라고 부른다.

 

스택의 기본동작

push	데이터를 추가
pop	가장 최근에 추가한 데이터를 제거하고 반환
top	가장 위의 데이터를 확인 (제거하지 않음)
inEmpty	스택이 비어 있는지 확인
isFull	스택이 가득 찼는지 확인

 

스택의 ADT (추상 자료형)

스택은 흔히 ADT로 정의된다.

ADT란 인터페이스만 정의되어 있고, 구현은 숨겨진 자료형을 뜻한다.

쉽게 말해서, 스택이 어떤 동작을 해야 하는지는 정해져 있지만, 그 구현 방식은 사용자에게 감춰져 있다는 것이다.

어떻게 동작해야 하는지의 명세만 제공하고, 실제 구현은 다양하게 할 수 있다.

 

스택 문제 1. 괄호 짝 맞추기

문제 설명

소괄호는 짝을 맞춘 열린 괄호 '('와 닫힌 괄호 ')'로 구성합니다. 문제에서는 열린 괄호나 닫힌 괄호가 마구 뒤섞인 문자열을 줍니다. 이때 소괄호가 정상으로 열고 닫혔는지 판별하는 solution() 함수를 구현하세요.
만약 소괄호가 정상적으로 열고 닫혔다면 true를, 그렇지 않다면 false를 반환하면 됩니다.

제약 조건
- 열린 괄호는 자신과 가장 가까운 닫힌 괄호를 만나면 상쇄됩니다.
- 상쇄 조건은 열린 괄호가 먼저 와야하고, 열린 괄호와 닫힌 괄호 사이에 아무것도 없어야 합니다.
- 더 상쇄할 괄호가 없을 때까지 상쇄를 반복합니다.

입출력의 예

s	반환값
(())()	True
((())()	False

문제 분석하기

해당 문제와 같은 경우에서 스택을 사용하면 좋다.
제약 조건에서, 가장 가장 가까운이라는 키워드를 보고 스택을 떠올리는 감각이 있어야 한다!
1. 문자열을 앞에서 하나씩 보며 열린 괄호가 나오면 푸시
2. 닫힌 괄호가 나오면 팝 연산을 통해 문자열에서 열린 괄호, 닫힌 괄호 한 쌍을 상쇄
3. 1~2를 마지막 문자열까지 반복해 스택에 열린 괄호가 남아 있다면 짝이 맞지 않은 것(false)이고, 괄호가 남아 있지 않다면 짝이 맞은 것(true)으로 판단

 

정답

function solution(s) {
	const stack = [];
    for (const c of s) {
    	if (c === "("){
        	stack.push(c);
        } else if (c === ")") {
        	if (stack.length === 0){
            	return false;
            } else {
              stack.pop();
            }
        }
    }
    
    retrun stack.length === 0;
}