[Codility] Lesson 7 : Brackets - JAVA

문제

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 consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".
 
Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(String S)에 입력되는 문자열의 길이(N) 0 ~ 200,000이고,
문자열은 "(", ")", "{", "}", "[, "]으로만 구성되어 있다.

빈 문자열이거나 "{}", "()", "[]"이 쌍을 이룰 때 적절하게 중첩되었다고 판단한다.
예를 들어 "{[()()]}"이면 중첩되었다고 볼 수 있지만 "([)()]"이면 적절히 중첩되었다고 볼 수 없다.

이때 문자열이 적절히 중첩되었을 경우 숫자 1을, 아닌 경우 숫자 0을 반환해주면 된다.

 

풀이 - 1

import java.util.Stack;
class Solution {
    public int solution(String S) {
        Stack<Character> chStack = new Stack<Character>();
        for(int i=0; i<S.length(); i++) {
            char ch = S.charAt(i);
            if(ch == '{' || ch == '[' || ch == '(') {
                chStack.push(ch);
            } else {
                if(chStack.empty()) return 0;
                if(ch == '}' && chStack.pop() != '{') return 0;
                if(ch == ']' && chStack.pop() != '[') return 0;
                if(ch == ')' && chStack.pop() != '(') return 0;
            }
        }
        return chStack.isEmpty() ? 1 : 0;
    }
}

 

'풀이 - 1'에 대한 회고

 

Stack 문제는 처음이므로 조금 고민해보다가 바로 다른 사람들이 어떻게 풀었는지 참고했다.

먼저 풀이를 설명하면

문자열에서 "{", "[", "("를 만나면 stack에 넣는다.
그리고 "}", "]", ")"을 만나면 stack에서 데이터를 pop하는데
이때 "{"와 "}", "["와 "]", "("와 ")"가 적절히 매칭되는지 판단한다.

만약 매칭되지 않으면 적절히 중첩된 문자열이 아니기 때문에 0을 바로 반환해주면 된다.
그리고 stack에 혹시나 데이터가 남아있으면 적절히 중첩된 것이 아니기 때문에 이때도 0을 반환한다.

마지막으로 stack에 남아있는 데이터가 없는 경우 적절히 중첩된 것으로 판단하여 1을 반환한다.

 

 

결과는 100%!

Stack, Queue 등의 알고리즘을 많이 풀어봐야겠다.