Lesson 7 - Nesting

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:

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

---

내 답안

저번에 봤던 문제라 똑같은 문제인데 첫풀이때는 성공하지 못했다.(퍼포먼스 모두 실패)

이유는 "적절하게 중첩"이 중간에 체크되었을 경우, 이전 글자는 체크할 필요 없다는 사실을 깨닫지 못하고 O(N)² 으로 풀려고 했던게 문제가 되었다.

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 == '(') {
                stack.push(nextChar);
            } else {
                if (stack.empty()) {
                    return 0;
                }

                lastChar = stack.pop();

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