[프로그래머스 / C++] 괄호 회전하기

문제

괄호 회전하기 : 문제 링크

문제 분석

• 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의한다.

• (), [], {} 는 모두 올바른 괄호 문자열이다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열이다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열이다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열이다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열이다.

• 대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어진다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성

• 제한 사항

• s의 길이는 1 이상 1,000 이하이다.

• 문자열 회전시키므로, 원형 수열과 비슷하다고 생각하고 문제에 접근. 올바른 괄호 문자열이 되게 하는 x의 개수를 저장할 정수형 변수 answer을 0으로 초기화. 이중 for loop를 사용하여 외부 loop는 s의 첫번째부터 마지막까지 순회하고, 괄호 시작을 저장할 char형 벡터 check와 올바른 괄호 문자열인지 확인할 bool형 isCorrect를 true로 초기화
• 내부 loop는 각 시작 요소에서 가능한 모든 연속 부분 수열을 순회. 현재 인덱스가 벡터의 크기를 초과하지 않으면서 회전하면서 요소를 순회하기 위해, 인덱스 j에서 s의 크기를 나눈 나머지를 저장할 정수형 변수 idx를 초기화. if문을 사용하여 s에서 현재 인덱스의 원소가 '(', '{', '['라면 check에 저장. 이외의 경우 else문을 사용하고, 내부에 if문을 통해 check가 빈 배열이거나 현재 인덱스의 원소가 ')', '}', ']' 인데 check의 마지막 원소가 맞는 짝이 아니라면 isCorrect를 false로 저장하고 loop 탈출. else 문을 통과했다면 맞는 괄호 짝을 찾았으므로 check의 마지막 원소를 제거. 내부 loop 탈출 후, if문을 사용하여 isCorrect가 true이고 check가 빈 배열이라면 올바른 괄호 문자열임을 뜻하므로 answer을 1씩 늘림. 외부 loop 탈출 후, 최종적으로 저장된 answer을 return

풀이

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 0;
    
    for(int i = 0; i < s.size(); ++i) {
        vector<char> check;
        bool isCorrect = true;
        for(int j = i; j < i + s.size(); ++j) {
            int idx = j % s.size();
            if(s[idx] == '(' || s[idx] == '{' || s[idx] == '[') 
                check.push_back(s[idx]);
            else {
                if(check.empty() || 
                  (s[idx] == ')' && check.back() != '(') || 
                  (s[idx] == '}' && check.back() != '{') || 
                  (s[idx] == ']' && check.back() != '[')) {
                    isCorrect = false;
                    break;
                }
                check.pop_back();
            }
        }
        if(isCorrect && check.empty()) answer++;
    }
    return answer;
}