문제 링크
내 풀이
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char ch : s.toCharArray()) {
if (ch == ')' || ch == '}' || ch == ']') {
if (stack.isEmpty()) {
return false;
}
char peeked = stack.peek();
if (ch == ')' && peeked == '(') {
stack.pop();
continue;
}
if (ch == '}' && peeked == '{') {
stack.pop();
continue;
}
if (ch == ']' && peeked == '[') {
stack.pop();
continue;
}
return false;
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
}
최적화
- 시간복잡도
- 공간복잡도
- peek을 pop으로 변경하여 중복 호출을 줄였다.
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char ch : s.toCharArray()) {
switch (ch) {
case ')':
if (stack.isEmpty() || stack.pop() != '(') return false;
break;
case '}':
if (stack.isEmpty() || stack.pop() != '{') return false;
break;
case ']':
if (stack.isEmpty() || stack.pop() != '[') return false;
break;
default:
stack.push(ch);
}
}
return stack.isEmpty();
}
}