Codility - Brackets

https://codility.com/demo/results/demoU2WQCE-QXU/

Task description 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. Assume that: N is an integer within the range [0..200,000]; string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")". Complexity: expected worst-case time complexity is O(N); expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

---------------------------------- 풀이 --------------정리전-----------------

Code: 13:04:39 UTC, java, final, score: 100.00

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556

// 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
        /*
        문제:
        입력되는 문자열 S가 괄호 순서가 맞으면 1을 출력
        순서가 맞지 않으면 0을 출력
        
        방법:
        스택을 이용한다.
        입력되는 괄호는 (,{,[ , ],},) 이다.
        
        1, 입력되는 S를 순서대로 스택에 넣는다
        2. 스택에 넣을때는 열리는 괄호만 넣는다
        3. 닫히는 괄호를 만났을때 마지막으로 들어간 괄호와 짝이 맞는지 확인한다.
        3-1. 짝이 맞지않으면 순서가 맞지않는 것으로 본다.
        */
        Stack stack = new Stack<String>();
        String opening = "({[";
        String closing = ")}]";
        
        if(S.length() % 2 != 0){
            return 0;
        }
        
        for(int i = 0; i < S.length(); i++){
            if(opening.indexOf(S.charAt(i)) != -1){
                stack.push(S.charAt(i));
            }
            else{
                // 스택이 비어있으면 0으로 끝난다.
                if(stack.empty())
                    return 0;
                
                // 스택에 최근에 넣은 괄호와 짝이 맞지 않으면 0을 출력
                if(opening.indexOf(stack.peek().toString()) != closing.indexOf(S.charAt(i))){
                    return 0;
                }
                
                stack.pop();
            }
                
        }
        if(!stack.empty())
            return 0;
        
        return 1;
        
    }
}

Analysis

Detected time complexity:
O(N)

test	time	result
Example tests
example1  example test 1	1.468 s	OK
example2  example test 2	1.444 s	OK
Correctness tests
negative_match  invalid structures	1.532 s	OK
empty  empty string	1.464 s	OK
simple_grouped  simple grouped positive and negative test, length=22	1.344 s	OK
Performance tests
large1  simple large positive test, 100K ('s followed by 100K )'s + )(	0.976 s	OK
large2  simple large negative test, 10K+1 ('s followed by 10K )'s + )( + ()	1.340 s	OK
large_full_ternary_tree  tree of the form T=(TTT) and depth 11, length=177K+	1.816 s	OK
multiple_full_binary_trees  sequence of full trees of the form T=(TT), depths [1..10..1], with/without some brackets at the end, length=49K+	1.420 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.444 s	OK