[Codility - Java] 7. Stacks and Queues - 3. Nesting

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

방법 1. Stack 이용

S는 "(" 나 ")"로 구성되어있습니다.
S가 비어있거나 적절하게 중첩되어있을 경우 1을 리턴하고, 아닐 경우에는 0을 리턴합니다.

문자열의 각 문자를 차례로 확인하면서 문자가 (일 경우 스택에 push하고
)일 경우 pop합니다.

pop하려할 때, 만약 스택이 빈상태라면 오류이므로 0을 리턴하고

모든 문자를 확인한 후 최종적으로 스택이 빈상태라면 괄호 짝이 맞는 상태이므로 1을 리턴, 스택안에 문자열이 남아 경우라면 (가 더 많은 상태이므로 0을 리턴합니다

static int nesting(String S) {
    if(S == null) return 1;
    Stack<Character> s = new Stack<>();
    for (char c : S.toCharArray()) {
        if ('(' == c) {
            s.push('(');
        } else if (s.empty()) {
            return 0;
        } else {
            s.pop();
        }
    }
    return s.empty() ? 1 : 0;
}

$O(N)$

방법 2. count 이용

문자열의 각 문자를 차례로 확인하면서 문자가 (일 경우 cnt를 증가시키고
)일 경우 cnt를 감소시키는 방식으로 stack을 대체할 수 있습니다.

static int nesting(String S) {
    if(S == null) return 1;
    int cnt = 0;
    for (char c : S.toCharArray()) {
        if ('(' == c) {
            cnt++;
        } else if (cnt == 0) {
            return 0;
        } else {
            cnt--;
        }
    }
    return cnt == 0 ? 1 : 0;
}

$O(N)$

EraseAdjacentLetters