[PS] 올바른 괄호

오늘부터 코딩테스트 역량을 복구하기 위해서 매일 프로그래머스 한 문제씩 풀기로 했다.

문제

풀이과정

이 문제는 ( 열리는 경우는 아예 신경 쓰지 않아도 괜찮다. 마지막에 괄호를 담는 자료구조가 empty인지 체크만 하면 되기 때문이다.

다만 )가 나올때가 케이스가 갈리는데
1) 자료구조의 가장 끝에 있는 원소가 (일 경우

• 끝의 원소를 pop 하면 된다.
  2) 가장 끝에 잇는 원소가 없는 경우
• 이 ) 는 영원히 짝지어질 요소가 없기 때문에 바로 false를 반환한다.

왜 자료구조로 stack을 선택했는가?

이 문제의 특징은 '('로 열리면 ')'로 닫혀야 한다는 것이다.
')' 문자가 나올 때 검사해야할 요소는 바로 직전에 들어간 원소가 '('인가 이다. 그래야 짝을 지을 수 있기 때문이다. 따라서 가장 최근에 들어간 원소가 무엇인지, 그 원소를 바로 빼내는데 유리한 자료구조가 필요했고 따라서 stack을 선택했다.

전체 코드

#include<string>
#include <iostream>
#include <stack>

using namespace std;

bool solution(string s)
{
    stack<char> st;
    
    for(char c : s)
    {
        if(c == '(')
        {
            st.push(c);
        }
        else //c == ')'
        {
            if(st.empty()) return false;
            char top = st.top();
            if(top == '(') st.pop();
        }
    }

    return st.empty();
}