[올바른 괄호/LV2/Python3, C++]

올바른 괄호 LV2

 

문제 설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어"()()" 또는 "(())()"는 올바른 괄호입니다.")()(" 또는 "(()("는 올바르지 않은 괄호입니다.'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

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




입출력 예

arr	answer
[1, 1, 3, 3, 0, 1, 1]	[1, 3, 0, 1]
[4, 4, 4, 3, 3]	[4, 3]

 

알고리즘 고득점 Kit의 스택/큐 문제 중 하나이다.

 

열린 괄호를 스택에 계속 쌓는다.

닫힌 괄호가 나오면 스택에 열린 괄호가 있는지 확인한다.

열린 괄호가 없다면 false를 즉시 반환한다.

 

모든 s를 돈 후에 스택이 비어있다면 true, 그렇지 않다면 false를 반환한다.

열린 괄호 하나이기 때문에 스택을 사용하지 않고, 정수형 변수를 통해서도 풀이가 가능하다.

 

 

C++의 경우 정수형 변수 하나를 통해서 풀이하였다.

#include<string>
#include <iostream>

using namespace std;

bool solution(string s)
{
    int cnt = 0;
    for(char c : s)
    {
        if (c == '(') ++cnt;
        else if (cnt == 0) return false;
        else --cnt;
    }

    return cnt==0;
}

 

 

Python3의 리스트를 사용하여 스택처럼 풀이하였다.

def solution(s):
    q = []
    for v in s:
        if v == "(":
            q.append(v)
            continue
        
        if q and q[-1] == "(":
            q.pop()
            continue
        
        return False

    return not q

 

 

---