[프로그래머스] - 올바른 괄호(C++)

올바른 괄호

오늘은 올바른 괄호 문제를 다뤄보겠습니다. 이 문제는 스택/큐에 속하는 문제로, 정답률 78%입니다.

 

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

 

• "()()" 또는 "(())()" 는 올바른 괄호입니다.
• ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

 

제한사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.

 

입출력 예

s	answer
"()()"	true
"(())()"	true
")()("	false
"(()("	false

 

시작 코드

#include<string>
#include <iostream>

using namespace std;

bool solution(string s)
{
    bool answer = true;

    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    cout << "Hello Cpp" << endl;

    return answer;
}

 

나의 풀이

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

using namespace std;

// 문자열 s가 올바른 괄호면 true, 아니면 false를 리턴하는 함수 작성
// 스택을 사용해 괄호 '('를 만나면 push, ')'를 만나면 pop을 하여 올바른 괄호 판별
bool solution(string s)
{
    // step 1 : 스택 생성
    stack<char> Stack;
    
    // step 2 : 스택에 괄호 넣기
    for(char &c : s)
    {
        if(c == '(')
        {
            Stack.push(c);
        }
        else if(c == ')')
        {
            if(Stack.empty()) // 앞에 '(' 괄호가 없다면
            {
                return false;
            }
            else
            {
                Stack.pop();
            }
        } 
    }

    return Stack.empty(); // 비어있다면(올바른 괄호) true, 비어있지 않다면(올바르지 않은 괄호) false
}

 

코드 분석

문자열 타입의 스택을 생성하고, s를 반복문으로 돌려 검사합니다. 만약 '(' 라면 스택에 해당 요소를 추가해줍니다. 만약 ')' 라면, 다시 if문에 들어가서 empty()함수를 통해 스택이 비어있는지 체크하고 비어있다면 false를 반환합니다. 비어있지 않다면 스택의 요소를 pop()으로 제거합니다. 반복문을 빠져나오면 스택이 비어있는지 체크하여 true 혹은 false를 반환하도록 합니다.

 

풀이 설명

문제에서 원하는 것은 올바른 괄호 찾기 입니다. 여기서 말하는 올바른 괄호는 "()" 이런식으로 열린 괄호와 닫힌 괄호가 세트로 이루어진 것을 의미합니다. 정확하게 문제에서 요구하는 것은 주어진 s를 검사해서 올바른 괄호인지 아닌지 판단하여 true 혹은 false를 반환하라는 것입니다. 첫번째 입출력 예로 설명하겠습니다. 문자열 s를 돌리면 처음에 '(' 를 만나서 스택에 추가되고, 바로 빠져나가 다음으로 넘어갑니다. 다음은 ')' 를 만나 else if에 들어가게 되고, 스택이 비어있지 않으므로 스택의 요소를 pop합니다. 그럼 '(' 가 빠져나오게 됩니다. 이렇게 되면 스택은 비어있는 상태가 되고, 예제 1번은 같은 괄호방식이 한번 더 반복 되므로 결국 마지막엔 스택은 비어있게 되어 true를 반환하게 됩니다.

 

<NEXT>

오늘은 프로그래머스 레벨2 "올바른 괄호" 문제를 다뤄봤습니다. 다음에는 연습문제 "최솟값 만들기" 문제로 찾아오겠습니다. 감사합니다.