👓 문제 설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
- "()()" 또는 "(())()" 는 올바른 괄호입니다.
- ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
💣 제한 사항
- 문자열 s의 길이 : 100,000 이하의 자연수
- 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
🚨 접근 방법
그림을 그려가며 해결 방법을 찾아 보았다.
첫번째 풀이 방법은 스택 a에 우선 문자열 s를 전부 저장한다.
a의 top이 ')'일 때 연속된 ')' 개수를 cnt++하면서 pop한다.
a의 top이 '('일 때 연속된 '(' 개수를 cnt-- pop한다.
위 두 반복문을 마친 후 cnt!=0일 때 정답이 false가 된다.
이 풀이를 했을 때 바깥에 있는 ()의 경우는 셀 수 없음을 알았고 다른 방법을 고려했다.
해결 방법으로는 '('일 때만 스택에 push, ')'일 때는 pop을 한다.
pop을 할 때 스택이 비어있으면 false!
문자열s에 대해 모든 탐색이 완료되었지만 스택이 비어있지 않다면 false!
두 가지 경우에 false로 설정하니 정답을 맞혔다.
🚈 풀이
#include <string>
#include <iostream>
#include <stack>
using namespace std;
bool solution(string s)
{
bool answer = true;
stack<char> a;
for(auto p:s){
if(p=='('){
cout<<p;
a.push(p);
}
else{
if(a.empty()){
answer=false;
break;
}
else{
a.pop();
}
}
}
if(!a.empty()){
answer=false;
}
return answer;
}