Codility - Nesting

Task description

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.

Assume that:

• N is an integer within the range [0..1,000,000];
• string S consists only of the characters "(" and/or ")".

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(1) (not counting the storage required for input arguments).

-------------------------------------풀이---------------------------------

Code: 13:25:29 UTC, java, final, score: 100.00

123456789101112131415161718192021222324252627282930313233343536373839404142434445

// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(String S) {
        // write your code in Java SE 8
        /* 
        문제:
        Brackets 문제와 유사하다, 하지만 공간복잡도가 O(1)이고 괄호는 소괄호만 있다.
        괄호쌍이 모두 맞으면 1을 출력, 틀리면 0을 출력한다.
        
        방법:
        1. 입력된 문자열의 개수가 홀수면 쌍이 맞지 않는다.
        2. 열린 괄호의 경우는 +1, 닫힌괄호는 -1을 한다
        3. 최종 카운터가 0이면 쌍이 맞는다.
        */
        int bracket_count = 0;
        
        // 괄호의 개수가 홀수면 쌍이 맞지 않는다.
        if(S.length() % 2 != 0)
            return 0;
            
        for(int i = 0; i < S.length(); i++){
            if(S.charAt(i) == '('){
                bracket_count ++;
            }
            else if(S.charAt(i) == ')'){
                bracket_count --;// ------------- ())( 의 경우도 있기 때문에//--------------  만약 마이너스값이 나오면 잘못된 경우다
                if(bracket_count < 0)
                    return 0;
            }
            else{ // 다른 괄호가 입력될 경우 잘못된 입력이므로 0을 출력한다.
                return 0;
            }
        }
        
        if(bracket_count != 0)
            return 0;
        else
            return 1;
    }
}

Analysis

Detected time complexity:
O(N)

test	time	result
Example tests
example1  example test	1.484 s	OK
example2  example test2	1.524 s	OK
Correctness tests
negative_match  invalid structure, but the number of parentheses matches	1.436 s	OK
empty  empty string	1.456 s	OK
simple_grouped  simple grouped positive and negative test, length=22	1.084 s	OK
Performance tests
large1  simple large positive test, 10K ('s followed by 10K )'s + )(	1.468 s	OK
large2  simple large negative test, 10K+1 ('s followed by 10K )'s + )( + ()	1.504 s	OK
large_full_ternary_tree  tree of the form T=(TTT) and depth 11, length=177K+	1.468 s	OK
multiple_full_binary_trees  sequence of full trees of the form T=(TT), depths [1..10..1], with/without unmatched ')' at the end, length=49K+	1.448 s	OK
broad_tree_with_deep_paths  string of the form (TTT...T) of 300 T's, each T being '(((...)))' nested 200-fold, length=120K+	1.460 s	OK