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

올바른 괄호

문제 링크

올바른 괄호

분석

문자열 s가 주어지며, 오직 ‘(‘ 혹은 ‘)’ 문자만으로 이루어져있습니다.
해당 문자열의 괄호가 올바른지 올바르지 않은지 판단하여 true 혹은 false를 반환해야합니다.

올바른 괄호 문자열이란 다음과 같습니다.

1. 어떤 ‘(‘가 나왔다면 대응되는 ‘)’가 나와야합니다.
2. 닫는 괄호인 ‘)’가 여는 괄호 ‘(‘ 없이 먼저 나와서는 안됩니다.
3. 전체 검사 후에도 여는 괄호에 대응되는 닫는 괄호가 없어서는 안됩니다.

스택을 사용하거나 괄호의 수를 세는 카운터 변수를 사용해볼 수 있습니다.
저는 공간 복잡도를 고려해 카운터 변수를 사용해보았습니다.

풀이

#include <string>
#include <vector>

using namespace std;

bool solution(string s)
{
    bool answer = true;
    
    // 열린 괄호의 수를 세는 변수
    int count = 0;
    
    // 문자열 순회
    for (int i = 0; i < s.length(); ++i)
    {
        // 현재 인덱스가 열린 괄호인 경우
        if (s[i] == '(')
        {
            ++count;
        }
        // 현재 인덱스가 닫힌 괄호인 경우
        else
        {
            --count;
            
            // 닫힌 괄호의 수가 더 많다면 올바르지 않은 괄호
            if (count < 0)
            {
                answer = false;
                break;
            }
        }
    }
    
    // 괄호의 수가 딱 맞지 않다면 올바르지 않은 괄호
    // 열린 괄호의 수가 더 많을 수 있기 때문에 한번더 확인한다.
    if (count != 0)
    {
        answer = false;
    }

    return answer;
}

성능 요약

시간 복잡도는 $O(n)$입니다.

• 문자열을 순회하는 반복문 $O(n)$

공간 복잡도는 추가적인 공간을 사용하지 않기 때문에 $O(1)$입니다.

테스트 성능

정확성 테스트

테스트 1 〉 통과 (0.01ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 4.22MB)
테스트 3 〉 통과 (0.01ms, 4.21MB)
테스트 4 〉 통과 (0.01ms, 3.7MB)
테스트 5 〉 통과 (0.01ms, 4.16MB)
테스트 6 〉 통과 (0.01ms, 4.02MB)
테스트 7 〉 통과 (0.01ms, 4.2MB)
테스트 8 〉 통과 (0.01ms, 4.14MB)
테스트 9 〉 통과 (0.01ms, 3.71MB)
테스트 10 〉 통과 (0.01ms, 4.08MB)
테스트 11 〉 통과 (0.01ms, 4.16MB)
테스트 12 〉 통과 (0.02ms, 4.14MB)
테스트 13 〉 통과 (0.01ms, 4.23MB)
테스트 14 〉 통과 (0.01ms, 4.45MB)
테스트 15 〉 통과 (0.01ms, 3.68MB)
테스트 16 〉 통과 (0.01ms, 3.67MB)
테스트 17 〉 통과 (0.01ms, 4.15MB)
테스트 18 〉 통과 (0.01ms, 4.21MB)

효율성 테스트

테스트 1 〉 통과 (0.35ms, 3.8MB)
테스트 2 〉 통과 (0.38ms, 3.84MB)