문제
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([])"
Output: true
Constraints:
1 <= s.length <= 104sconsists of parentheses only'()[]{}'.
https://leetcode.com/problems/valid-parentheses
풀이
괄호의 열고 닫힘의 validation을 체크하는 것으로, 소/중/대 괄호에 대한 열고 닫힘이 연속되어야 하는 것이다.
(마지막에 소괄호를 열었으면 소괄호로 닫아야 한다)
이에 Stack을 이용해서 String을 char array로 변환하여 순환하면서, 열림 괄호가 나오면 Stack에 담고 닫힘 괄호가 나왔을 때 동일한 괄호가 나왔는지 확인하도록 했다.
확인하는 방법은 각 괄호에 대해 아스키 값을 확인해 보니 1 또는 2의 차이가 있는 점을 이용하여 닫힘 괄호가 나왔을 때 Stack의 pop 결과와의 차이가 1이나 2가 아닌 경우 실패로 처리했다.
-> ( : 40, ) : 41, { : 123, } : 125, [ : 91, ] : 93
또한 String에 닫힘 괄호만 있는 등 열림 괄호가 닫힘 괄호보다 개수가 적게 있을 경우 pop할 때 Stack이 비어있기에 에러가 날 수 있다는 상황에 대한 예외 처리도 진행했다.
코드
class Solution {
public boolean isValid(String s) {
Stack<Character> valid_stack = new Stack<>();
for(Character c : s.toCharArray()) {
if(c.equals('(') || c.equals('{') || c.equals('[')) {
valid_stack.push(c);
} else {
if(valid_stack.isEmpty()) {
return false;
}
char compare_c = valid_stack.pop();
if(c - compare_c > 2 || c - compare_c < 1) {
return false;
}
}
}
return valid_stack.isEmpty();
}
}
결과
Runtime : 3 ms
Memory Usage : 41.47 MB
'LeetCode' 카테고리의 다른 글
| 19. Remove Nth Node From End of List (0) | 2025.01.22 |
|---|---|
| 18. 4Sum (0) | 2025.01.17 |
| 17. Letter Combinations of a Phone Number (0) | 2025.01.14 |
| 16. 3Sum Closest (0) | 2025.01.09 |
| 15. 3Sum (0) | 2025.01.07 |
