문제 링크
1. 아이디어
문자열을 왼쪽부터 훑으면서, 닫는 괄호가 나올 때마다 아직 짝을 못 찾은 여는 괄호가 앞에 있는지 확인한다. 끝까지 읽었을 때 짝을 못 찾은 여는 괄호가 하나도 남지 않아야 올바른 괄호다.
괄호 문제를 해결하는 대표 방식인 스택 풀이는 여는 괄호를 스택에 쌓고 닫는 괄호를 만나면 스택에서 하나 꺼낸다. 닫는 괄호인데 스택이 비어 있으면 짝지을 여는 괄호가 없다는 뜻이라 그 자리에서 올바르지 않음을 알 수 있다. 문자열을 끝까지 읽은 뒤 스택이 비어 있어야 모든 여는 괄호가 닫힌 것이다.
깊이 카운터 풀이는 괄호가 한 종류뿐이라는 점을 이용한다. 스택에 쌓이는 값이 항상 (로 같아서 꺼낼 때 종류를 따질 일이 없어서, 결국 스택의 내용은 안 쓰이고 높이만 의미가 있다. 스택을 정수 카운터 하나로 바꿔 여는 괄호에서 늘리고 닫는 괄호에서 줄이면 같은 판정을 공간 $O(1)$로 줄일 수 있다. 카운터가 0인데 닫는 괄호를 만나면 )(처럼 짝 없이 닫힌 경우이고, 끝까지 읽은 뒤 카운터가 0이어야 한다.
2. 복잡도
| 접근 | 시간 | 공간 |
|---|
| 스택 | $O(N)$ | $O(N)$ |
| 깊이 카운터 | $O(N)$ | $O(1)$ |
($N$ = s의 길이)
3. 코드
풀이 1: 스택 [Java][C++][Python]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| import java.util.*;
class Solution {
boolean solution(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(c);
} else {
if (stack.isEmpty()) return false;
stack.pop();
}
}
return stack.isEmpty();
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include <bits/stdc++.h>
using namespace std;
bool solution(string s) {
stack<char> st;
for (char c : s) {
if (c == '(') {
st.push(c);
} else {
if (st.empty()) return false;
st.pop();
}
}
return st.empty();
}
|
1
2
3
4
5
6
7
8
9
10
11
| def solution(s):
stack = []
for c in s:
if c == "(":
stack.append(c)
else:
if not stack:
return False
stack.pop()
return not stack
|
풀이 2: 깊이 카운터 [Java][C++][Python]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
boolean solution(String s) {
int cnt = 0;
for (char c : s.toCharArray()) {
if (c == '(') {
cnt++;
} else {
if (cnt == 0) return false;
cnt--;
}
}
return cnt == 0;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include <bits/stdc++.h>
using namespace std;
bool solution(string s) {
int cnt = 0;
for (char c : s) {
if (c == '(') {
cnt++;
} else {
if (cnt == 0) return false;
cnt--;
}
}
return cnt == 0;
}
|
1
2
3
4
5
6
7
8
9
10
11
| def solution(s):
cnt = 0
for c in s:
if c == "(":
cnt += 1
else:
if cnt == 0:
return False
cnt -= 1
return cnt == 0
|