프로그래머스 - 올바른 괄호(c++, javascript)

문제 설명

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

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

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

 

 

제한사항

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

 

입출력 예

 

입출력 예 설명

입출력 예 #1,2,3,4
문제의 예시와 같습니다.

 

풀이

이 문제는 읽고나서 스택으로 푸는 생각이 가장 먼저 떠올랐다.

문자열의 앞에서부터 탐색하면서

여는 괄호를 발견하면 스택에 쌓고 닫는 괄호를 발견하면 괄호쌍이 되므로 쌓아두었던 스택의 top을 없앤다.

모든 괄호를 비교했다면 마지막에 stack의 크기를 확인해서 비어있다면 모두 쌍이 만들어졌다는 의미이므로 true를 리턴했다.

 

c++

#include <vector>
#include <string>
using namespace std;

bool search(int i, string s){
    vector<char> stack;
    
    while(i != s.size()){
        if( s[i] == '(' ) stack.push_back(s[i]);
        if( !stack.empty() && s[i] == ')') stack.pop_back();
        ++i;
    }
    
    // 모두 쌍이 완성됐다는 의미이므로 true를 리턴한다.
    if(stack.empty()) return true;
    return false;
}

bool solution(string s)
{
    bool answer = true;
    
    // 문자열의 첫번째 원소가 ')'라면 쌍이 만들어질 수 없으므로 바로 false를 리턴한다.
    if( s[0] == ')' ) return false;
    
    answer = search(0, s);
    
    return answer;
}

 

javascript

function search(i, s){
    const stack = [];
    
    while(i != s.length){
        if( s[i] == '(' ) stack.push(s[i]);
        if( s[i] == ')' ) stack.pop();
        ++i;
    }
    
    if(!stack.length) return true;
    return false;
}

function solution(s){
    let answer = true;

    if( s[0] == ')' ) return false;
    
    answer = search(0, s);

    return answer;
}