[C++] 백준(BOJ) - 15926 : 현욱은 괄호왕이야!!
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
여는 괄호 ‘(’와 닫는 괄호 ‘)’로 구성된 문자열에서 아래의 조건을 만족하는 문자열을 올바른 괄호 문자열이라고 부른다.
- () 는 올바른 괄호 문자열이다
- 어떤 문자열 x가 올바른 괄호 문자열이라면, (x)도 올바른 괄호 문자열이다.
- 어떤 문자열 x와 y가 올바른 괄호 문자열이라면, xy도 올바른 괄호 문자열이다.
현욱은 친구로부터 생일 선물로 굉장히 긴 괄호 문자열을 받았다(도대체 왜 이런 걸 선물하는걸까?). 하지만 현욱은 올바른 괄호 문자열이 아니면 굉장히 싫어하기 때문에, 받은 괄호 문자열에서 연속한 일부분을 잘라서 올바른 괄호 문자열을 만들려고 한다. 그리고 이왕이면 긴 문자열이 좋으니 현욱은 부분 구간을 최대한 길게 잘라내려고 한다. 현욱을 도와 주어진 괄호 문자열에서 위의 조건을 만족하는 가장 긴 부분 문자열의 길이를 계산하는 프로그램을 작성해보자.
입력
첫 줄에 문자열의 길이 n (1 ≤ n ≤ 200,000)이 주어진다.
둘째 줄에 괄호로만 구성된 길이 n짜리 문자열이 주어진다.
출력
주어진 문자열에서 길이가 가장 길면서 올바른 괄호 문자열인 부분 문자열의 길이를 출력한다. 올바른 괄호 문자열인 부분 문자열을 찾을 수 없는 경우 0을 출력한다.
알고리즘
- 문자열
- 스택
- 배열
풀이
배열을 활용
- 올바른 괄호 영역은 1로 아닌 부분은 0으로 채워진 일차원 배열을 만들어서 일차원 배열이 가장 길게 1로 이루어진 부분을 리턴스택만을 사용 - 스택에 분기점 (-1) 을 시작 부분에 삽입해 준 후 올바른 괄호가 나올 때마다 인덱스의 차를 구해가며 최대값을 구하고, ‘(‘ 가 스택에서 모두 없어졌을 때는 분기점을 초기화해가며 최대값을 계속해서 다시 구하는 알고리즘을 구성
코드 1 - 배열
// BOJ-15926 : 현욱은 괄호왕이야!!
#include<bits/stdc++.h>
using namespace std;
int n, res, cnt, d[200001];
string s;
stack<int> stk;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> s;
for (int i = 0; i < n; i++)
{
if (s[i] == '(') stk.push(i);
else if (stk.size())
{
d[i] = d[stk.top()] = 1;
stk.pop();
}
}
for (int i = 0; i < n; i++)
{
if (d[i])
{
cnt++;
res = max(res, cnt);
}
else cnt = 0;
}
cout << res << '\n';
return 0;
}
코드 2 - 배열
// BOJ-15926 : 현욱은 괄호왕이야!!
#include<bits/stdc++.h>
using namespace std;
int n, res;
string s;
stack<int> stk;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> s;
stk.push(-1);
for (int i = 0; i < n; i++)
{
if (s[i] == '(') stk.push(i);
if (s[i] == ')')
{
stk.pop();
if (!stk.empty())
{
res = max(res, i - stk.top());
}
else stk.push(i);
}
}
cout << res << '\n';
return 0;
}
평가
- 일차원 배열을 활용하여 문제 풀이를 하는 방법이 비교적 간단하지만 스택만을 이용해 다양한 방식으로 문제 풀이를 할 수 있다는 것을 학습
