개발기록장

괄호 회전하기

6 min read

문제 링크
난이도 : Lv. 2

문제 내용

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다. (), [], {} 는 모두 올바른 괄호 문자열입니다. 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다. 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다. 대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 s의 길이는 1 이상 1,000 이하입니다. 입출력 예

입출력 예 설명 입출력 예 #1 다음 표는 ”[](){}” 를 회전시킨 모습을 나타낸 것입니다. x s를 왼쪽으로 x칸만큼 회전 올바른 괄호 문자열?

올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다. 입출력 예 #2

올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다. 입출력 예 #3 s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다. 입출력 예 #4 s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

문제 분석

올바른 괄호가 나오면 삭제하기 위해 스택을 사용함.
특정 인덱스부터 시작해서 순환하는 형태로 스택에 데이터를 넣기 위해 함수를 만듬
좀 더 보기 편하게 나는 괄호에 숫자를 부여해서, top 데이터랑 다음 데이터가 더해서 0이 되면 사라지게 했음.
(는 1, )는 -1 이런식으로

작성한 코드

// 250407
 
#include <string>
#include <vector>
#include <stack>
#include <iostream>
 
using namespace std;
vector<int> bToi(string s) {
    vector<int> arr(s.size());
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == '(') arr[i] = 1;
        else if(s[i] == ')') arr[i] = -1;
        else if(s[i] == '[') arr[i] = 2;
        else if(s[i] == ']') arr[i] = -2;
        else if(s[i] == '{') arr[i] = 3;
        else if(s[i] == '}') arr[i] = -3;
    }
    return arr;
}
 
bool IsGoodStr(vector<int> &arr, int start) {
    stack<int> st;
    int i = start;
    // cout << "Start index : " << i << endl;
    int count = 0;
    while(count < arr.size()) {
        if(arr[i] > 0) {
            st.push(arr[i]);
        }
        else {
            if(st.empty()) return false;
            else {
                // cout << "Top : " << st.top() << " Next : " << arr[i] << endl;
                if(st.top() + arr[i] == 0){
                    st.pop();  
                } 
                else {
                    return false;
                }
            }
        }
        i++;
        if(i > arr.size() - 1) i = 0;
        count++;
    }
    if(st.empty()) {
        /*
        cout << "Start Index " << start << " is Good Str" << endl;
        */
        return true;
    }
    
    else {
        // cout << "Start Index " << start << " is Not Good Str" << endl;
        return false;}
}
 
 
int solution(string s) {
    vector<int> arr = bToi(s);
    /*
    cout << "To Int : " ;
    for(int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    */
    int answer = 0;
    for(int i = 0; i < arr.size(); i++) {
        stack<int> st;
        if(IsGoodStr(arr, i)) answer++;
    }
    return answer;
}

우수 코드 분석

// 프로그래머스 책 참고
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
 
using namespace std;
 
unordered_map<char char> bracketPair = {{')', '('}, {']', '['}, {'}', '{'}};
 
bool isValid(string &s, int start) {
    stack<char> stk;
    unsigned int sz = s.size();
 
    for(int i = 0; i < sz; i++) {
        char ch = s[(start + i) % sz];
        if (bracketPair.count(ch)) {
            if (stk.empty() || stk.top() != bracketPair[ch])
                return false;
            stk.pop();
        } else stk.push(ch);
    }
 
    return stk.empty();
}
 
int solution (string s){
    int answer = 0;
    int n = s.size();
 
    for(int i = 0; i < n; i++){
        answer += isValid(s, i);
    }
 
    return answer;
}

unordered_map 에서 요소를 찾을 때 count, find를 사용하는데,
count는 해당 키를 가진 요소의 갯수를 출력하고
find는 이터레이터를 반환하기 때문에 이후 처리가 조금 다름.
여기서는 있냐 없냐가 중요했기 때문에 count를 사용했음.
키값을 닫힌 괄호로 했음. 그래서 저 위에 count(ch)는 닫힌 괄호냐 아니냐 라는 의미를 가짐
나는 괄호를 숫자화 한거고, 여기 예제는 괄호를 맵으로 구성한 것임.

그래프 뷰