백준 9012번 괄호

문제 링크입니다: https://www.acmicpc.net/problem/9012

알고리즘 분류는 스택으로 분류되어있지만 단순 문자열을 이용하여 푼 문제였습니다.

알고리즘은 아래와 같습니다.

1. '(' 괄호가 오면 cnt를 1 증가시키고 ')' 괄호가 오면 cnt를 1 감소시킵니다.

2. cnt가 0보다 작아지면 정상적인 괄호 문자열이 아니기 때문에 false를 반환합니다. ex) ())(

3. 문자열을 다 순회하면 cnt가 0인 경우와 아닌 경우를 살펴봐야합니다.

i) cnt가 0이라면 정상적인 괄호 문자열이였기 때문에 true를 반환합니다.

ii) cnt가 0이 아니라면 정상적인 괄호 문자열이 아니였기 때문에 false를 반환합니다.

#include <iostream>

#include <string>

using namespace std;

 

bool parenthesis(string s)

{

        int cnt = 0;

 

        for (int i = 0; i < s.size(); i++)

        {

 

                 if (s[i] == '(')

                         cnt++; // 스택의 크기 증가

                 else

                         cnt--; // 스택의 크기 감소

                 if (cnt < 0)

                         return false; //스택의 크기가 음수가 된다면 안됨

        }

 

        if (cnt == 0)

                 return true;

        else

                 return false;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        int test_case;

        cin >> test_case;

 

        for(int t=0; t<test_case; t++)

        {

                 string s;

                 cin >> s;

                

                 if (parenthesis(s))

                         cout << "YES" << "\n";

                 else

                         cout << "NO" << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~