[백준 C++] 4949 - 균형잡힌 세상

괄호 짝 맞추는 문제입니다. 여러 방법이 있지만, 이 풀이에서는 스택을 이용합니다.

 

괄호의 규칙은 아래와 같습니다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

 

따라서 괄호는 ( value ), [ value ] 와 같은 형태는 가능하지만,

( value ], [ value ) 와 같은 형태나 서로 매칭되지 괄호가 존재하지 않을 경우일 때 규칙에 위배됩니다.

 

우선, cin은 공백에서 입력이 끝나므로 getline을 이용한 입력을 받으셔야 합니다.

int main() {
    string s;
    getline(cin, s);
}

 

이를 통해 문자열 s에 문장 하나를 입력합니다. 그 후에 이 문자열을 체크하는 함수를 작성합니다.

int checker(string s) {
    stack<char> st;

    for(auto i:s) {
        switch(i) {
            case '(':
            case '[':
                st.push(i);
            break;
            
            case ')':
            case ']':
                if(st.empty()) return 0;

                if(i == ')' && st.top() == '(') st.pop();
                else if(i == ']' && st.top() == '[') st.pop();
                else return 0;
            break;
        }
    }

    if(!st.empty()) return 0;
    return 1;
}

for(int i=0; i<s.length(); i++)와 char c = s[i]; 대신 범위 기반 for문인 for(auto i:s)를 이용합니다. 그 다음 오류의 유무를 검색합니다. 그 다음의 switch 문은 if/else로 바꾸어 쓸 수 있습니다.

 

괄호 시작인 '(', '[' 는 st에 원소를 추가, 괄호 끝인 ')', ']'는 스택의 제일 끝 원소를 삭제 혹은 오류를 반환합니다.

여기서 일단 괄호의 시작과 끝, 짝이 맞는지 체크를 진행합니다. ')'이 오면 '(', ']'이 오면 '['이 맞는지 체크합니다.

이 경우가 아닐 경우 오류를 반환합니다.

 

그리고 20%대 TC에서 '틀렸습니다'를 받을 수 있는 처리가 필요합니다.

모든 끝맺음 괄호는 처리했지만, 처음 시작하는 괄호가 남아 있을 경우에는 균형잡힌 문자열이 아니게 됩니다.

그것이 마지막 stack의 내부가 비었는지 체크하는 부분입니다.

 

이렇게 전체 코드가 완성됐습니다.

 

위의 코드로 통과할 수 있었습니다. (제출번호 37169543) 필요한 부분에 참고가 되었길 바랍니다.

 

 

주의

solved.ac에서 다른 사람의 소스 코드를 그대로 혹은 수정을 가해 제출하는 행위는 제재를 받으실 수 있습니다.