https://school.programmers.co.kr/learn/courses/30/lessons/76502
문제 해결 과정
착안
스택(stack) 자료 구조를 활용하여 다음과 같은 과정을 통해 괄호 문자열 여부를 판단하고, 해당 과정을 회전된 문자열에 대해서 반복 수행함으로써 괄호 문자열의 수를 카운팅한다.
- '(', '{', '[' 문자가 주어지는 경우: 스택에 해당 문자를 추가한다.
- ')', '}', ']' 문자가 주어지는 경우: 스택이 비어있거나 스택의 top에 위치한 문자가 괄호로 짝지어지지 않는 경우 false를 반환한다. 그렇지 않다면 스택에서 top에 위치한 문자를 제거한다.
- 모든 문자열에 대해 위의 과정이 끝난 다음 스택이 비어있으면 true, 그렇지 않다면 false를 반환한다.
구현
주어진 길이 $n$의 괄호 문자열을 회전시키는 과정은, 편의상 주어진 문자열을 복사하여 뒤에 이어 붙인 뒤 해당 문자열의 $i$번째부터 시작하는 길이 $n$의 부분 문자열을 구하는 substr() 함수를 활용하였다.
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
더보기
#include <string>
#include <stack>
using namespace std;
stack<char> Stack;
bool decision(string s)
{
for (char c : s)
{
switch (c)
{
case '(': case '{': case '[':
{
Stack.push(c);
break;
}
case ')':
{
if (Stack.empty() || Stack.top() != '(') return false;
Stack.pop();
break;
}
case '}':
{
if (Stack.empty() || Stack.top() != '{') return false;
Stack.pop();
break;
}
case ']':
{
if (Stack.empty() || Stack.top() != '[') return false;
Stack.pop();
break;
}
}
}
return Stack.empty();
}
int solution(string s)
{
int answer = 0;
int n = s.size();
s += s;
for (int i = 0; i < n; i++)
if (decision(s.substr(i, n)))
answer++;
return answer;
}
실행 결과
'C++ 코딩 문제 풀이 > 프로그래머스' 카테고리의 다른 글
[Programmers] 프로세스 (1) | 2023.12.02 |
---|---|
[Programmers] 튜플 (0) | 2023.09.25 |
[Programmers] 호텔 대실 (0) | 2023.09.07 |
[Programmers] 연속 펄스 부분 수열의 합 (0) | 2023.09.07 |
[Programmers] 멀리 뛰기 (0) | 2023.08.30 |
댓글