Lesson 7 - Brackets

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 ')'.

---

문제는 전부 해석했는데 30분 안에 통과시키는 로직을 못만들어서 그냥 바로 답을 참조했다.

stack에 Char배열을 담아서 중첩된 글자가 시작되는 (, [, { 는 바로 stack에 넣고

반대되는 글자인 경우, 중첩됐다고 가정했을때는 시작글자가 반드시 존재하기 때문에 검사, 만약 stack에 아무것도 없다면 중첩이 안됐을거라는 조건으로 작성한 답이다.

베스트 답안

import java.util.Stack;
class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<>();
        char lastChar;
        for (char nextChar : S.toCharArray()) {
            if (nextChar == '(' || nextChar == '[' || nextChar == '{') {
                stack.push(nextChar);
            } else {
                if (stack.empty()) {
                    return 0;
                }

                lastChar = stack.pop();

                if (nextChar == ')' && lastChar != '(') {
                    return 0;
                } else if (nextChar == ']' && lastChar != '[') {
                    return 0;
                } else if (nextChar == '}' && lastChar != '{') {
                    return 0;
                }
            }
        }
        return stack.isEmpty() ? 1 : 0;
    }
}