문제
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)으로 비교적 적절한 성능을 낸다.
아마 다른 사람들도 비슷하게 문제를 풀었을 거라 생각하고 다음 문제 풀어야지!