[Lv2] 올바른 괄호

문제

해당 문제 해결 전 자료 구조에 대해서 알고싶으신 분들은 아래 포스팅 참고해주시면 됩니다.

시퀀스 자료구조 — 배열·연결 리스트·스택·큐

자료구조를 ‘창고 정리법’에 비유해 시퀀스 구조의 본질을 설명합니다. 배열·연결 리스트·스택·큐의 메모리 배치와 연산 특성, 선택 기준을 간단한 STL 코드(std::array/list/stack/queue)로 정리했습니다.

Gibeom KimGibeom Kim

문제

문제 설명

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

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

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

제한사항

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

입출력 예

입출력 예 설명

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

풀이1) std::string을 stack처럼 사용

std::string의 마지막 character를 가져와서, 왼쪽 방향 괄호 여부를 카운트한다. 왼족이면 +1) 오른쪽이면 -1)을 해주는데, 끝나기 전에 -로 바뀌면( 오른쪽이 더 많으면) false / 끝나고 나서 0이 아니면(즉, 왼쪽이 더 많으면 ) false, 끝까지 무사히 도달하면 true를 반환하도록 한다.

#include <string>

bool solution(const std::string & s)
{
    int left_count = 0;

    for (char c : s)
    {
        left_count += (c == '(') ? 1 : -1;
        if (left_count < 0)
        {
            return false; // 닫는 괄호가 더 많아짐
        }
    }
    return left_count == 0;
}

풀이2) std::stack을 사용

이 경우 stack을 사용해서, 왼쪽 괄호가 오는 경우에 push, 오른쪽 괄호가 오는 경우에 비어있는지 체크한 뒤 pop을 해준다. pop을 하기 전 비어있으면 바로 false를 내보내고, 마지막에 비어있지 않으면 마찬가지로 false를 리턴한다. 마지막에 최종적으로 비어 있어야지 TRUE를 반환하도록 한다.

#include <stack>
#include <string>

bool solutionStack(const std::string &s)
{
    std::stack<char> st;
    for (char c : s)
    {
        if (c == '(')
        {
            st.push(c);
        }
        else
        {
            if (st.empty())
            {
                return false;
            }
            st.pop();
        }
    }
    return st.empty();
}