이번에는 백준 15926번 현욱은 괄호왕이야!! 문제를 풀어보았습니다.
처음에는 올바르게 매칭되는 괄호만 표시한 뒤, 가장 길게 이어지는 구간을 찾는 방식으로 구현해보았습니다.
이후에는 스택에 인덱스를 저장하면 현재 위치에서 가장 긴 올바른 괄호 문자열의 길이를 바로 구할 수 있다는 점을 이용하여 다시 구현하였습니다.
문제 설명
괄호 문자열이 주어집니다.
이 문자열에서 연속된 부분 문자열 중 올바른 괄호 문자열이 되는 가장 긴 길이를 구하는 문제입니다.
올바른 괄호 문자열이 없다면 0을 출력합니다.
풀이 아이디어
V1
먼저 괄호가 서로 올바르게 매칭되는 위치를 모두 찾았습니다.
매칭되는 괄호는 true, 그렇지 않은 괄호는 false로 표시하였습니다.
이후 true가 가장 길게 연속되는 구간의 길이를 계산하여 정답을 구하였습니다.
V2
스택에 괄호의 인덱스를 저장하는 방식으로 구현하였습니다.
닫는 괄호를 만났을 때 현재 매칭되는 가장 가까운 여는 괄호를 제거하고,
현재 인덱스와 스택의 top 인덱스 차이를 계산하면 현재 위치에서 만들 수 있는 가장 긴 올바른 괄호 문자열의 길이를 구할 수 있습니다.
이를 이용하여 최대 길이를 갱신하였습니다.
V1 코드
#include <bits/stdc++.h>
using namespace std;
bool flag[200000];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string s;
int n;
cin >> n >> s;
stack<int> stk;
for (int i=0; i<n; i++) {
if (s[i] == '(')
stk.push(i);
else if (s[i] == ')') {
if (!stk.empty()) {
flag[stk.top()] = true;
flag[i] = true;
stk.pop();
}
}
}
int ret = 0;
int cnt = 0;
for (int i=0; i<n; i++) {
if (flag[i]) {
cnt++;
ret = max(ret, cnt);
}
else {
cnt = 0;
}
}
cout << ret << '\n';
return 0;
}V1 풀이 흐름
- 문자열을 입력받습니다.
- 스택을 이용하여 괄호가 올바르게 매칭되는 위치를 찾습니다.
- 매칭되는 괄호를
true로 표시합니다. true가 연속되는 가장 긴 길이를 계산합니다.- 최댓값을 출력합니다.
V1 구현 포인트
1. 올바른 괄호 표시
여는 괄호의 인덱스를 스택에 저장하였습니다.
if (s[i] == '(')
stk.push(i);닫는 괄호를 만났을 때 매칭되는 괄호가 있다면 두 위치를 모두 true로 표시하였습니다.
flag[stk.top()] = true;
flag[i] = true;2. 가장 긴 연속 구간 계산
true가 연속되는 길이를 계산하였습니다.
if (flag[i]) {
cnt++;
ret = max(ret, cnt);
}
else {
cnt = 0;
}중간에 false가 등장하면 다시 길이를 0으로 초기화하였습니다.
V2 코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
string s;
cin >> n >> s;
stack<int> stk;
stk.push(-1);
int ret = 0;
for (int i=0; i<n; i++) {
if (s[i] == '(') {
stk.push(i);
}
else {
stk.pop();
if (stk.size()) {
ret = max(ret, i - stk.top());
}
else {
stk.push(i);
}
}
}
cout << ret << '\n';
return 0;
}V2 풀이 흐름
- 스택에
-1을 먼저 넣습니다. - 여는 괄호의 인덱스를 스택에 저장합니다.
- 닫는 괄호를 만나면 스택을 pop합니다.
- 스택이 비어있지 않다면 현재 길이를 계산합니다.
- 스택이 비어있다면 현재 위치를 기준점으로 다시 저장합니다.
- 최댓값을 출력합니다.
V2 구현 포인트
1. 스택에 인덱스 저장
스택에는 괄호가 아닌 인덱스를 저장하였습니다.
stack<int> stk;
stk.push(-1);-1은 처음 기준점을 의미합니다.
2. 여는 괄호 저장
여는 괄호를 만나면 현재 인덱스를 저장하였습니다.
if (s[i] == '(')
stk.push(i);이후 닫는 괄호가 나왔을 때 매칭할 위치가 됩니다.
3. 현재 길이 계산
닫는 괄호를 만나면 먼저 pop을 수행하였습니다.
stk.pop();이후 스택이 비어있지 않다면
ret = max(ret, i - stk.top());를 이용하여 현재 위치까지의 가장 긴 올바른 괄호 문자열의 길이를 계산하였습니다.
4. 기준점 갱신
스택이 비어있다는 것은 현재 닫는 괄호와 매칭되는 여는 괄호가 없다는 의미입니다.
따라서 현재 위치를 새로운 기준점으로 저장하였습니다.
if (!stk.size()) {
stk.push(i);
}이후의 길이 계산은 이 위치를 기준으로 다시 시작하게 됩니다.
V2는 V1보다 공간을 덜 사용하면서도, 괄호가 매칭되는 위치를 별도로 표시하지 않고 현재 위치에서 가장 긴 올바른 괄호 문자열의 길이를 바로 계산할 수 있다는 점이 핵심입니다.
