다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.
이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.
> 입력
대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다.
- '(', '[', '{' : 스택에 push
- 나머지 경우(')', ']', '}')
- 스택이 비었는지(짝의 개수가 맞지않는 경우)
- 같은 경우인지(짝의 모양이 맞지않는 경우)
를 제외한 경우에만 answer(올바른 괄호 모양)값을 증가시켜준다.
- 왼쪽으로 한 칸씩 땡기기
#include <string>
#include <vector>
#include <stack>
using namespace std;
int solution(string s) {
int answer = 0, size = s.size();
while(size--) {
bool exit = true;
stack<char> a;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(' || s[i] == '{' || s[i] == '[') a.push(s[i]);
else {
if (a.empty()) {
exit = false;
break;
}
switch (s[i]) {
case ')':
if (a.top() == '(') a.pop();
else exit = false;
break;
case '}':
if (a.top() == '{') a.pop();
else exit = false;
break;
case ']':
if (a.top() == '[') a.pop();
else exit = false;
break;
}
}
if (!exit) break;
}
if (a.empty() && exit) answer++;
char b = s[0];
s = s.substr(1, s.size() - 1) + b;
}
return answer;
}
회전을 일일이 다 하느라 딱히 시간복잡도가 좋지 못하다. 더 좋은 방법을 찾아보는걸로