![스택을 활용한 수식의 괄호 쌍](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbLegHK%2FbtrMNTufh4Y%2FEXp4F97USAtlUoebVh1ZP0%2Fimg.png)
수식의 괄호 쌍
많이 나오는 문제는 아닌거 같지만, 전에 봤던 코딩테스트에서 못풀었던 기억이 있어서 공부해봤다.
( ) ( ) ( )
위와 같은 괄호가 있다면 잘 맞아떨어지는 올바른 괄호의 쌍이다.
( ) ) ( )
위와 같은 괄호는 가운데 ' ) ' 때문에 쌍이 안맞기 때문에 올바르지 못한 괄호의 쌍이다.
이 문제는 가장 마지막에 담긴 원소랑 비교를 해야하기 때문에 스택을 사용하면 적합하다.
여는 괄호일때는 스택에 Push를 해서 담아주고,
닫는 괄호일때는 스택의 top을 확인해서 쌍이 맞는지 확인해주고 맞으면 Pop해주면 된다.
괄호 쌍이 틀린 조건들
1. 닫는 괄호를 만났는데 스택이 비어있는 경우 (여는 괄호가 앞에 없었다는 뜻)
2. 닫는 괄호를 만났는데 짝이 안맞는 경우( 닫는 괄호로 대괄호를 만났는데 스택의 top에는 소괄호가 있는경우)
3. 탐색을 끝냈는데 스택이 비어있지 않은경우 (여는 괄호를 스택에 담았지만 닫는 괄호가 없어서 pop하지 못한경우)
문제 풀어보기 - 4949번: 균형잡힌 세상 (acmicpc.net)
4949번: 균형잡힌 세상
하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다
www.acmicpc.net
주어진 문자열을 검사해서 괄호의 쌍이 올바르면 "yes"를 출력하고, 괄호의 쌍이 올바르지 못하면 "no"를 출력한다.
예제의 7번째 줄처럼 . 앞에 공백만 있고 괄호는 없어도 yes를 출력해야 하고,
' . ' 마침표 하나만 있을때 이 과정을 종료해야 한다.(종료할땐 yes/no 출력하면 안됨)
#include<iostream>
#include<string>
#include<stack>
using namespace std;
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
while (true)
{
bool check = true;
stack<char> Res;
string s;
getline(cin, s);
if (s == ".") break;
for (auto e : s)
{
if (e == '(' || e == '[') Res.push(e);
else if (e == ')')
{
if (Res.empty() || Res.top() != '(')
{
check = false;
break;
}
Res.pop();
}
else if (e == ']')
{
if (Res.empty() || Res.top() != '[')
{
check = false;
break;
}
Res.pop();
}
}
if (!Res.empty()) check = false;
if (check) cout << "yes\n";
else cout << "no\n";
}
return 0;
}
1. 현재 문자열이 맞는지 확인할 bool값 check와 스택을 선언하고 스트링으로 문자열을 입력 받는다.
2. 공백이 포함되어 있기 때문에 getline을 이용해서 입력을 받았다.
3. 문자열에 마침표 하나만 있다면 끝났다는 뜻이니 break로 while문을 탈출한다.
4. 입력받은 스트링을 쭉 돌면서 검사를 시작하는데, 여는 괄호를 만나면 스택에 push를 해준다.
5. 닫는 괄호를 만나면 비어있는지, 짝이 맞지않는지 검사 둘중에 하나라도 참이라면 bool값을 false로 바꾸고 for문을 탈출한다.
6. 아니라면 스택을 pop해준다.
7. 과정을 다 끝내고도 스택이 비어있지 않다면 bool 값을 false로 바꿔준다.
8. bool 값이 true라면 "yes" , false라면 "no"를 출력한다.
처음에는 문자열을 한번에 다 받아서 마침표를 이용해 나눠서 판단하는줄 알고 애를 먹었는데 아니였다.
다른 알고리즘의 공부가 끝나면 여러 문제들을 또 풀어봐야겠다.
'프로그래밍 공부 > 코딩테스트 준비' 카테고리의 다른 글
백준 4179번 - 불! (0) | 2022.09.24 |
---|---|
#6 코테준비 - BFS(Breadth First Search) (0) | 2022.09.23 |
#5 코테준비 - 덱(Deque) (0) | 2022.09.23 |
#4 코테준비 - 큐(Queue) (0) | 2022.09.23 |
#3 코테준비 - 스택(Stack) (0) | 2022.09.22 |
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!