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

문제 URL

https://school.programmers.co.kr/learn/courses/30/lessons/76502

프로그래머스

[문제 설명]

이 문제는 대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어진다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켜 만든 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 반환하는 문제이다.

 

 

[문제 풀이]

스택의 push, pop을 이용하여 짝이 맞는 괄호를 찾아주면 되는 문제였다.

 

[어려웠던 점]

• 처음에는 올바른 괄호마다 push, pop을 해줄 때 count를 이용하여 push, pop의 횟수가 s의 size와 같다면 일치하는 방식으로 코드를 짜려고 했는데 변수 없이도 가능할 것 같아서 구글링을 통해 다른 풀이를 찾아봤다. 

다른 풀이에서 확인한 결과, 결국 스택이 empty일 때 올바른 괄호 문자열이 되는 것이기 때문에 이를 활용하면 됐다. 또한, 스택이 비어있는데 문자가 닫는 괄호라면 무조건 올바른 괄호 문자열이 될 수 없으므로 이 경우에는 빠르게 실패로 판단했다.

 

• 또 다른 점은 문자열을 왼쪽으로 x칸만큼 회전시키는 함수를 만들었는데, 반복문을 반복하면 어차피 문자열은 한 칸씩 회전하게 되었다. 따라서 이 방식으로 하면 너무 효율이 떨어졌다. 이에 다시 한 칸을 회전시키는 함수를 작성해 주었다.

이 과정에서 string의 erase()와 push_back() 함수를 사용할 수 있다는 것을 깨달았다.

---

#include <string>
#include <vector>
#include <stack>
using namespace std;

/*
string rotate(string s, int x){  // 문자열을 왼쪽으로 x칸만큼 회전시키는 함수
    string tmp1 = "";
    string tmp2 = "";
    bool isBehind = false;
    
    for(char i : s){
        if(i == s[x])
            isBehind = true;
        if(isBehind)
            tmp2 += i;
        else
            tmp1 += i;        
        tmp2 += tmp1;
        
        return tmp2;
    }
}
*/
string rotate(string s){  // 문자열을 왼쪽으로 1칸 회전시키는 함수
    string res = s;
    char temp = res[0];
    
    res.erase(0,1);
    res.push_back(temp);
    
    return res;
}

bool isCheck(string s){
    stack<char> st;
    
    for(char ch : s){
        if(ch == '[' || ch == '{' || ch == '(')
            st.push(ch);
        else{
            if(st.empty())
                return false;
            else{
                if(ch == ']' && st.top() == '[')
                    st.pop();
                else if(ch == '}' && st.top() == '{')
                    st.pop();
                else if(ch == ')' && st.top() == '(')
                    st.pop();
            }
        }
    }
    if(!st.empty())
        return false;
    else
        return true;
}

int solution(string s) {
    int answer = 0;
        
    for(int i=0; i<s.size(); i++){
        s = rotate(s);

        if(isCheck(s))
            answer++;
    }

    return answer;
}

 

참고: https://transferhwang.tistory.com/525