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:
(Copyright 2009–2023 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.)
import java.util.*;
class Solution {
public int solution(String S) {
Stack<Character> stack = new Stack<>();
for (char c : S.toCharArray()) {
if (c == '{' || c == '[' || c == '(') {
stack.push(c);
} else {
if (stack.isEmpty()) return 0;
char last = stack.pop();
if (last == '{' && c != '}') return 0;
if (last == '[' && c != ']') return 0;
if (last == '(' && c != ')') return 0;
}
}
if (!stack.isEmpty()) return 0;
return 1;
}
}
나중에 들어간 괄호가 먼저 닫힌다 -> 후입선출 -> stack