[Codility] Lesson 7 : Nesting - JAVA

문제

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 consists only of the characters "(" and/or ")".

Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

 

문제 해설

solution(String S)에 입력되는 문자열 S의 길이(N)는 0 ~ 1,000,000이고,
문자열 S는 "("과 ")'으로만 구성되어 있다.

문자열이 비어있거나, "()"인 경우 적절히 중첩되었다고 볼 수 있다.
예를 들어 S = "(()(())())"이면 적절히 중첩되었다고 판단하고,
S = "())" 이면 적절히 중첩되어있다고 판단하지 않는다.

이때 적절히 중첩된 문자열인 경우 숫자 1을, 아닌 경우 숫자 0을 반환한다.

 

풀이 - 1

import java.util.Stack;
class Solution {
    public int solution(String S) {
        Stack<Character> stack = new Stack<Character>();
        for(char ch : S.toCharArray()) {
            if(ch == '(') stack.push(ch);
            else {
                if(stack.isEmpty()) return 0;
                stack.pop();
            }
        }
        return stack.isEmpty() ? 1 : 0;
    }
}

 

'풀이 - 1'에 대한 회고

 

한 번 풀어봤던 문제라고 Stack을 이용해서 금방 풀었다.

역시 초반에 나오는 문제는 다른 사람의 소스코드를 참고하길 잘 했어.

 

이번 문제에서는 알고리즘이 바로 기억나서 작성했다.

 

 

다행히, 그리고 예상한대로 정확성과 퍼포먼스 모두 100%이다.

그리고 중요한 시간복잡도!

 

 

시간복잡도 또한 O(n)으로 비교적 적절한 성능을 낸다.

아마 다른 사람들도 비슷하게 문제를 풀었을 거라 생각하고 다음 문제 풀어야지!