[프로그래머스 Lv.2/ C++] 올바른 괄호

문제 - 올바른 괄호

프로그래머스

■ 문제 설명

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

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

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

 

■ 제한사항

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

 

 

풀이과정

이 문제에서 다음을 고려해야 한다.

1. 문자열을 앞에서부터 읽을 때 '(' 의 개수가 ')'보다 항상 같거나 많은지 확인하기
2. 모든 문자열을 읽은 후 '(' 와 ')'의 개수가 같은지 확인하기

 

 

1. 문자열을 앞에서부터 읽을 때 '(' 의 개수가 ')'보다 항상 같거나 많은지 확인하기

for (int i = 0; i < s.size(); i++) {
    if (s[i] == '(')
        n++;
    else
        n--;
    if (n < 0)
        return false;
}

괄호의 개수를 셀 변수 n을 둔고 문자열 앞에서부터 괄호를 읽는다. 매 반복마다 '('일 경우 n++, ')'일 경우 n-- 연산을 한 후 n의 값이 음수가 되는지 확인한다. 음수일 경우 ')'에 대한 '('의 짝이 부족하다는 뜻이다.

 

2. 모든 문자열을 읽은 후 '(' 와 ')'의 개수가 같은지 확인하기

[...]

if (n > 0)
    return false;

1. 의 과정을 지난 후 n의 값이 0보다 크면 ')'의 개수가 부족하다는 뜻이다.

 

 

전체 코드

#include <string>
#include <stack>

using namespace std;

bool solution(string s) {
    int n = 0;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(')
            n++;
        else
            n--;
        if (n < 0)
            return false;
    }

    if (n > 0)
        return false;

    return true;
}


int main() {

    string s = "((())())";
    bool b = solution(s);

    // print
    printf("%s", b ? "True" : "False");

    return 0;
}

---

GitHub - devminjae97/practice: Practice Programming, especially algorithm.

 

---

 

다른 풀이방법

이 문제는 Stack을 이용해서도 풀 수 있다.

n의 증감 연산 없이 stack의 push(), empty(), pop() 함수를 이용한다.

 

 

전체 코드

#include <string>
#include <stack>

using namespace std;

bool solution(string s) {
    stack<char> stck;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(')
            stck.push('(');
        else
            if (!stck.empty())
                stck.pop();
            else
                return false;
    }

    if (stck.size() > 0)
        return false;

    return true;
}


int main() {

    string s = "((())())";
    bool b = solution(s);

    // print
    printf("%s", b ? "True" : "False");

    return 0;
}

---

GitHub - devminjae97/practice: Practice Programming, especially algorithm.