https://www.acmicpc.net/problem/15926
15926번: 현욱은 괄호왕이야!!
첫 번째 입출력에서, 맨 처음 위치부터 4개를 잘라낸 (())가 가장 긴 올바른 괄호 문자열이다. 두 번째 입출력에서, 6번째 위치부터 8개를 잘라낸 ()((()))가 가장 긴 올바른 괄호 문자열이다.
www.acmicpc.net
주어진 입력에서 올바른 괄호쌍의 부분 문자열이 가장 긴 길이를 구하는 문제입니다.
올바른 괄호쌍을 구하기 위해서는 stack을 이용합니다.
기본 스택문제와 동일하게 `(`가 나오면 stack에 push, `)`가 나오면 stack에서 pop 연산을 수행합니다.
이 문제는 주어진 문자열의 인덱스를 이용합니다.
`(`가 나오면 그 인덱스를 stack에 push합니다.
`)`가 나오면 s.top의 인덱스와 현재 인덱스에 true 값을 넣습니다.
최종으로는 chk[i] = true인 부분의 max 길이를 구해주시면 되겠습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
#define MAX 200001
using namespace std;
string str;
bool chk[MAX];
int N;
void func() {
stack<int> s;
for (int i = 0; i < N; i++) {
if (str[i] == '(') {
s.push(i);
}
else {
if (s.empty()) continue;
chk[i] = chk[s.top()] = true;
s.pop();
}
}
int ret = 0;
int conn = chk[0];
for (int i = 1; i < N; i++) {
if (chk[i]) conn++;
else conn = 0;
ret = max(ret, conn);
}
cout << ret << '\n';
}
void input() {
cin >> N >> str;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 21939 문제 추천 시스템 Version 1 (0) | 2022.02.11 |
|---|---|
| boj 17299 오등큰수 (0) | 2021.02.22 |
| boj 9372 상근이의 여행 (0) | 2021.02.09 |
| boj 1158 요세푸스 문제 (0) | 2021.02.09 |
| boj 1918 후위 표기식 (0) | 2021.02.05 |