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

문제 설명

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

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

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

제한 사항

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

입출력 예

s	result
"[](){}"	3
"}]()[{"	2
"[)(]"	0
"}}}"	0

풀이

s.erase(), push_back()함수를 이용하여 string값 회전시키는 풀이입니다.

#include <string>
#include <vector>
#include <stack>

using namespace std;

int solution(string s) {
    int answer = 0;
    
    for(int i = 0; i < s.size(); i++){
        stack<char> st;
        bool flag = false;
        for(int j = 0; j < s.size(); ++j){
            if(s[j] == ']' && st.top() == '['){
                st.pop();
            }
            else if(s[j] == '}' && st.top() == '{'){
                st.pop();
            }
            else if(s[j] == ')' && st.top() == '('){
                st.pop();
            }
            else{
                flag = true;
                st.push(s[j]);
            }
        }
        if(st.empty() && flag){
            answer++;
        }
        char ch = s.front();
        s.erase(s.begin());
        s.push_back(ch);
    }
    
    
    return answer;
}

 

다른 풀이

std::rotate 함수를 사용하여 문자열을 회전시키는 풀이입니다.

std::rotate(s.begin(), s.begin() + 3, s.end());   // 3칸씩 왼쪽 이동

std::rotate(s.begin(), s.end() - 1, s.end());     // 1칸씩 오른쪽 이동

#include <string>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

inline bool check(const string& s){
    stack<char> st;
    for(const auto& it : s){
        if( it == '(' | it == '[' || it == '{'){
            st.push(it);
        }
        else if(st.empty()){
            return false;
        }
        else{
            switch(it){
                case ')' :{
                    if(st.top() == '('){
                        st.pop();
                    }
                    else{
                        return false;
                    }
                    break;
                }
                case ']':{
                    if(st.top() == '['){
                        st.pop();
                    }
                    else{
                        return false;
                    }
                    break;
                }
                case '}':{
                    if(st.top() == '{'){
                        st.pop();
                    }
                    else{
                        return false;
                    }
                    break;
                }
            }
        }
    }
    return st.empty();
}

int solution(string s) {
    int answer = 0;
    for(int i = 0; i < s.size(); ++i){
        if(check(s)){
            ++answer;
        }
        rotate(s.begin(), s.begin() + 1, s.end());
    }
    return answer;
}

 

다른 풀이

전달인자(argument)를 이어 붙여서 원래 전달인자 길이만큼 이동하면서 rotate처럼 사용하는 풀이입니다. 슬라이딩 윈도우같은 방법입니다.

#include <string>
#include <vector>
#include <stack>
#include <map>

using namespace std;

int solution(string s) {
    int answer = 0;
    
    int len = s.size();
    s += s;
    
    map<char, char> hash;
    hash['('] = ')';
    hash['['] = ']';
    hash['{'] = '}';
    
    for(int i = 0; i < len; i++){
        string str = s.substr(i, len);
        stack<char> st;
        bool check = false;
        for(const auto& it : str){
            if(it == '(' || it == '{' || it == '['){
                st.push(it);
            }
            else{
                if(st.empty()){
                    check = false;
                    break;
                }
                else{
                    if(hash[st.top()] == it){
                        st.pop();
                        check = true;
                    }
                    else{
                        check = false;
                        break;
                    }
                }
            }
        }
        if(st.empty() && check){
            answer++;
        }
    }
    
    return answer;
}