Lesson 7. Stacks and Queues - Nesting

1. 문제

A string S consisting of N characters is called properly nested if:
S is empty;
S has the form "(U)" where U is a properly nested string;
S has the form "VW" where V and W are properly nested strings.

For example, string "(()(())())" is properly nested but string "())" isn't.

Write a function:
  int solution(string &S);
that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise.

For example, given S = "(()(())())", the function should return 1 and given S = "())", the function should return 0, as explained above.
Write an efficient algorithm for the following assumptions:
  - N is an integer within the range [0..1,000,000];
  - string S is made only of the characters '(' and/or ')'.

 

중첩된 문제열인지 확인하는 문제. 

이전에 올렸던 Brackets 문제와 매우 유사하다.

 

예시)

return 0: 중첩아님, 

return 1: 중첩

문자열	return value
""	1
(U)	1
VW	1
(()(())())	1
())	1

 

2. 매개변수 조건

• String S 길이: 0 ~ 1,000,000
• String S 구성 문자 : '(' or ')'

 

3. 코드 (C++)

#include <stack>

int solution(string &S) {

    if(S.empty() || S.size() == 1) return 1; // 빈 문자열

    stack<char> stack = {};
    char top = {};

    for(size_t i = 0; i < S.size(); i++)
    {
        switch(S[i])
        {
            //괄호를 여는 문자는 무조건 삽입
            case '(':
                stack.push(S[i]);
                break;
            //괄호를 닫는 문자는 올바른 중첩인지 확인 필요
            case ')':
                top = stack.top();
                if(top != '(') return 0;
                stack.pop();
                break;
        }
    }

    if(stack.empty()) return 1; //최종적으로 stack이 비어야 올바른 중첩
    return 0;
}