문제 해결을 위한 관찰
"문자열을 앞에서부터 읽어나갈 때 닫는괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애 버리는 명령이라고 생각해도 된다."
문제 해결 방법
-
여는 괄호가 나오면 스택에 추가
-
닫는 괄호가 나왔을경우
스택이 비어있는지,top과 짝이 맞는지 확인 -
모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍, 남아있지 않으면 올바른 괄호 쌍
연습문제
4949 . 균형잡힌 세상
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
while (1)
{
string str;
getline(cin, str);
if (str.size() == 1 && str[0] == '.')
break;
stack <char> s;
bool bYes = 1;
for (char c : str)
{
if (c == '(')
{
s.push(c);
}
else if (c == ')')
{
if (s.empty())
{
bYes = 0;
break;
}
else
{
if (s.top() == '(')
{
s.pop();
}
else
{
bYes = 0;
break;
}
}
}
else if (c == '[')
{
s.push(c);
}
else if (c == ']')
{
if (s.empty())
{
bYes = 0;
break;
}
else
{
if (s.top() == '[')
{
s.pop();
}
else
{
bYes = 0;
break;
}
}
}
}
if(!s.empty())
bYes = 0;
if (bYes)
cout << "yes\n";
else
cout << "no\n";
}
}공백이 포함된 문자열을 입력으로받기때문에 getline을 통해 한줄을 입력받고 종료조건인 "." 들어오면 break를 통해 반복문을 탈출해준다
다음 범위기반 for문을통해 ()[]일경우 조건문을 걸어 검사한다 ([ 의 경우 스택에 push 해주고 ])의 경우는 스택이 비어있거나 top의 짝이 맞지않을경우 byes를 no로 만들고 넘어가준다 다음 마지막으로 스택이 비어있는지 확인해준다( 모든짝이맞다면스택이 비어있어야함)
10779 쇠막대기
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int ans = 0;
stack <char> s;
string str;
cin >> str;
for (int i = 0; i < str.size(); i++)
{
if (str[i] == '(')
{
if (str[i + 1] == ')')
{
ans += s.size();
i++;
}
else
{
s.push(str[i]);
}
}
else
{
s.pop();
ans++;
}
}
cout << ans;
}문자열을 저장할 str과 정답을 저장할 인트형 변수 ans 과 char저장할 스택을 선언해준다.
str에 입력을 받고 앞에서부터 탐색을 할때 (가이라면 두가지의 경우가있다 레이저이거나 쇠막대기의 시작점이거나 다음 문자가 )라면 레이저이므로 i++를 해주고 정답에 현재 스택의 사이즈를 더해준다 ( 레이저는 현재 쇠막대기를 2등분하므로 만약 3개가들어있다면 3개의 쇠막대기가 추가되는것과 같다 ) 아니라면 스택에 푸쉬를 해준다
다른입력은 )일경우 밖에없음으로 막대기의 끝이다 그렇기때문에 정답에 1을 더해주고 스택을 하나 pop해주면 된다.
2504 . 괄호의 값
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
stack <char> s;
string str;
cin >> str;
int ans = 0;
int temp = 1;
for (int i = 0; i < str.size(); i++)
{
if (str[i] == '(')
{
temp *= 2;
s.push(str[i]);
}
else if (str[i] == '[')
{
temp *= 3;
s.push(str[i]);
}
else if (str[i] == ')')
{
if (s.empty() || s.top() != '(')
{
cout << "0\n";
return 0;
}
if (str[i - 1] == '(')
{
ans += temp;
}
temp /= 2;
s.pop();
}
else if (str[i] == ']')
{
if (s.empty() || s.top() != '[')
{
cout << "0\n";
return 0;
}
if (str[i - 1] == '[')
{
ans += temp;
}
temp /= 3;
s.pop();
}
}
if (!s.empty())
{
cout << "0\n";
return 0;
}
cout << ans << '\n';
}다시 풀어봐도 어려운 문제라 전의 풀이를 참고했다 분배법칙을 사용해서 풀수있는 문제이다
이해하기 위해 기내식은 수박바님의 그림을 첨부하였다 (출처 : https://soobarkbar.tistory.com/151)
값을 바로 바로 정답에 더해주는것이아닌 중간값을 이용한다 중간값을 1로초기화되어있고
( [ 경우 각각 2와 3을 곱해준다 )] 를만난경우는 만약 바로 직전이 짝이맞는경우라면 중간값을 정답에 더해주고 스택을 pop해주고 중간값을 3으로 나누어준다 각각 의미를 다시 분석해보면
(일경우 2를 곱해주는 이유는 뒤에있는 () []들에 2를 곱해주는것이고 )] 의경우 짝이맞을땐 현재 중간값 만큼의 값을 짝을맞춘 괄호가 가지는것이니 정답에 더해준다 짝이 맞지 않는경우나 맞은경우 모두 괄호가 닫힌것이므로 해당하는 2,3으로 중간값을 나누어 주는것이다.
9012 . 괄호
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
while (n--)
{
stack <char> s;
string str;
cin >> str;
bool bCheck = 1;
for (char c : str)
{
if (c == '(')
{
s.push(c);
}
else
{
if (s.empty())
{
bCheck = 0;
break;
}
s.pop();
}
}
if (!s.empty())
bCheck = 0;
if (bCheck)
cout << "YES\n";
else
cout << "NO\n";
}
}기본적인 괄호쌍 문제이다 (는 스택에 넣어주고 )일경우 짝이맞는지 검사해주면된다 여기선 괄호의 형태가 하나이므로 스택이 비었는지만 검사해주면된다
