[Codility - Java] 7. Stacks and Queues - 1. Brackets

1. Brackets

Determine whether a given string of parentheses (multiple types) is properly nested.

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:

class Solution { public 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 ")".

---

문자열 S는 {, }, (, ), [, ]로만 이뤄져 있습니다.
S가 비어있거나, 괄호가 각각 열고 닫는 형태가 짝이 맞을 경우 1을 리턴하고 아닐 경우 0을 리턴합니다.

문자열의 각 문자를 반복문으로 도는데
여는 괄호인 {, (, [는 무조건 스택에 넣으면 되고
닫는 괄호인 }, ), ]가 나올경우, 스택의 맨 위(peek) 값이 짝에 해당되는 여는 괄호일 경우 pop을 하면서 반복문을 진행하고. 만일 스택이 비어있거나 다른 짝일 경우에는 짝이 안맞는 문자열이므로 바로 0을 리턴하며 함수 실행을 종료합니다.

peek함수는 Stack이 비어있을 때 실행할 경우 에러를 발생시키기 때문에 실행 전에 Stack이 비어있지 않은지 확인하는 과정이 필요합니다.

static int brackets(String S) {
    Stack<Character> s = new Stack<>();
    for (char c : S.toCharArray()) {
        switch (c) {
            case '{':
            case '[':
            case '(':
                s.push(c);
                break;
            case ')':
                if (s.empty() || s.peek() != '(') {
                    return 0;
                }
                s.pop();
                break;
            case ']':
                if (s.empty() || s.peek() != '[') {
                    return 0;
                }
                s.pop();
                break;
            case '}':
                if (s.empty() || s.peek() != '{') {
                    return 0;
                }
                s.pop();
                break;
        }
    }

    return s.size() > 0 ? 0 : 1;
}

$O(N)$