[프로그래머스/C++] 올바른 괄호 풀이

프로그래머스 : 올바른 괄호

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

프로그래머스

---

문제

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

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

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

 

제한사항

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

---

LIFO(Last In First Out) 구조를 따르는 스택 을 사용해서 푸는 문제.

 

문자열 하나씩 순회해서 여는 괄호 ( 일 경우에는 스택에 push,
닫는 괄호 ) 일 경우에는 스택에서 pop 한다. 이 때 스택이 비어있는 경우 false 를 반환한다.

 

마지막으로 최종 스택의 크기가 0보다 클 경우 (여는 괄호가 남아있을 경우) false 를 반환, 나머지 경우 true 를 반환한다.

---

풀이

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

using namespace std;

bool solution(string s)
{
    stack<int> stk;

    for(int i=0; i<s.length(); i++){
        if(s.at(i) == '('){
            stk.push(1);
        } else {
            if(stk.empty()){
               return false; 
            } else {
                stk.pop();
            }
        }
    }
    
    if(stk.empty()){
        return true;
    }

    return false;
}

 

다 풀고 나서 생각난 건데.. 굳이 스택을 쓸 이유가 없다.

괄호 수는 숫자로 세기만 해도 충분하다 

 

#include<string>
#include <iostream>

using namespace std;

bool solution(string s)
{
    int cnt = 0;
    for(int i=0; i<s.size(); i++){
        if( s.at(i)=='(' ){
            cnt++;
        } else {
            if(cnt<=0){
                return false;
            } else {
                cnt--;
            }
        }
    }

    if (cnt==0){
        return true;
    } else{
        return false;
    }
}

 

복잡하게 스택 라이브러리를 가져오지 않아도 문제는 잘 풀린다❗️

 

 

 

풀이 인증