[프로그래머스] 올바른 괄호 in C++

(제가 생각한 솔루션이므로 최적의 솔루션이 아닐 수 있습니다..! 피드백 환영합니다!)

 

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12909

1. 문제 이해

문제에서 주어지는 입력값은 총 한 개입니다.

 

입력값 이름	예시	타입	조건
s	"(())()"	string	100,000 이하의 길이

 

s 문자열은 ( 또는 ) 로 이루어져 있습니다.

 

이 문제에는 s 문자열의 괄호가 올바른 괄호인지 판단해야 합니다.

 

올바른 괄호는 ( 가 먼저 오고 그 다음 ) 가 같은 개수만큼 짝지어져 올 때 입니다.

 

2. 풀이법 연상

위와 같은 문제를 접할 때 가장 먼저 스택 구조가 생각났습니다.

 

( 문자를 만났을 때 스택에 Push 하고 ) 문자를 만났을 때 스택의 ( 문자를 Pop 해주어,

스택에 모든 ( 문자가 Pop 되었을 때 올바른 괄호임을 확인하면 된다고 생각했습니다.

 

다만 ( 또는 ) 문자에 대한 처리만 하기 때문에 이 문제만 한정해서 따로 스택을 만들 필요 없이 그냥 count 또는 sum를 가지고 ( 문자는 +1, ) 문자는 -1 해주면서 마지막에 0이면 올바른 괄호임을 확인할 수 있다고 생각했습니다.

 

예를 들어 올바른 괄호가 되지 않는 경우는 다음과 같을 것입니다.

1. ( 괄호가 완전히 닫히지 않은 경우, ex) (( )

2. ( 괄호가 없는데 ) 괄호가 있는 경우, ex) ( ))

 

1번의 경우 sum 이 0 보다 큰 경우이고, 2번의 경우, 0보다 작은 경우일 것입니다.

 

결국,

1) 스택을 이용하는 정석적인 방법

2) +1, -1을 통한 방법

 

총 두 가지를 모두 사용해보기로 했습니다.

 

3.  풀이에 필요한 지식

스택 구조는 STL의 stack 을 사용해서 구현이 가능합니다.

 

Stack은 대표적인 LIFO(Last In First Out) 형식의 자료 구조입니다.

 

다음과 같이 사용할 수 있습니다.

#include <stack>

stack<int> st;

st.push(1);
int pop_value = st.pop();

st.top(); // 스택의 top element
st.size(); // 스택 내 element의 개수
st.empty(); // 스택이 비어있는가?

 

4. 코딩

 

방법 1. 스택을 이용한 경우.

#include <string>
#include <stack>

using namespace std;

bool solution(string s)
{
    bool answer = true;
    int s_size = s.size();
    stack<char>  st;
    
    for(int i=0;i<s_size;i++){
        if(s[i] == '(')
            st.push('(');
        else{
            if(st.empty()) // 스택이 비어있지만 pop을 해야 하는 경우,
                return false;
            st.pop();
        }
    }
    if(!st.empty()) // 스택이 비어있지 않은 경우,
        answer = false;
    
    return answer;
}

 

방법 2. 스택을 이용하지 않은 경우.

#include <string>

using namespace std;

bool solution(string s)
{
    bool answer = true;
    int sum = 0;
    int s_size = s.size();
    for(int i=0;i<s_size;i++){
        if(s[i] == '(')
            sum += 1;
        else
            sum -= 1;
        
        if (sum < 0)
            return false;
    }
    
    if(sum != 0)
        answer = false;

    return answer;
}