Lesson 7. Stacks and Queues - Brackets

1. 문제

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:
  - S is empty;
  - S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
  - S has the form "VW" where V and W are properly nested strings.

For example, the string "{[()()]}" is properly nested but "([)()]" is not.

Write a function:
  int solution(string &S);

that, given a string S consisting of N characters, returns 1 if 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..200,000];
  - string S is made only of the following characters: '(', '{', '[', ']', '}' and/or ')'.

 

주어진 괄호 문자열(여러 종류의 괄호 포함)이 올바른 순서와 형태로 중첩되어 있는지 확인하는 문제

return 0: 잘못된 중첩 ( S = "([)()]" )

return 1: 올바른 중첩 ( S = "{[()()]}" )

 

2. 매개변수 제한

• 문자열 길이: 0 ~ 200,000
• 문자열을 구성하는 문자: '(', '{', '[', ']', '}', '/', ')'

 

3. 예제 분석

올바른 중첩 예제( S = "{[()()]}" )를 확인해보자.

index	문자	현재 문자 상태	비고
0	{	{
1	[	{[
2	(	{[(
3	)	{[	S[3]와 올바르게 중첩되는 문자로, S[3]와 함께 제거
4	(	{[(
5	)	{[	S[4]와 올바르게 중첩되는 문자로, S[4]와 함께 제거
6	]	{	S[1] 문자와 올바르게 중첩되는 문자로, 함께 제거
7	}		S[0]과 올바르게 중첩되는 문자로, 함께 제거

 

여기서 두 가지를 확인할 수 있다.

• 현재 문자 상태를 stack으로 관리하면 된다.
• 올바르게 중첩 된 문자는 최종적으로 빈 stack이 된다.

 

4. 주의할 점

빈 문자열이 입력되었을 때, 이는 올바른 중첩인가? 아닌가?

정답은 올바른 문자열이다.

왜냐하면 예제 분석에서 보았듯이, 올바르게 중첩된 문자는 최종적으로 빈 stack이 되기 때문이다.

즉, 빈 문자열이 입력되어서 빈 stack이 유지되든, 문자열을 다 처리 했는데 그 결과가 빈 stack 이든, 두 상태는 같은 상태이다. 

 

4. 코드 (C++)

#include <stack>

int solution(string &S) {

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

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

    for(size_t i = 0; i < S.size(); i++)
    {
        // '/' 문자는 쌍을 이루지 않아도 된다
        if(S[i] == '/') continue;

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

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