[프로그래머스] 괄호 회전하기 c++ (풀이, 코드, 스택)

문제 링크

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

프로그래머스

 

문제

 

 

코드 및 풀이

처음에는 너무 간단하게 소,중,대 괄호에 대해서 여는거면 ++ 닫는거면 -- 를 하면서 그냥 간단하게 반복문을 돌때 0미만이 하나라도 나오면 없는거 아니야? 라는 생각을 했습니다.

 

틀린 코드(오답 코드)

/*

괄호 회전하기

AB가 올바른 괄호 문자열 -> AB도 올바른 괄호 문자열

S가 X칸만큼 회전시켰을때 S가 올바른 괄호 문자열이 되게 하는 X개의 개수 return

소,중,대괄호의 구분 없이 일단 다 감싸지게만 되면 맞는거임

소중대 ({[

갯수를 하는데 닫는 괄호들이면 --, 여는 괄호들이면 ++을 함

그리고 갯수가 만약 0보다 작다는 것은 올바른 괄호가 아니라는것임을 다시 한번 더 증명 하는거라고 생각

일단 )}]에 대해서는 처음에 나오게 된다면 바로 올바르지 않은 문자열로 진행 그리고

한칸씩 전진시키면서 올바른 문자열을 추출

*/

#include <string>

#include <vector>

using namespace std;

int solution(string s) {

    int answer = 0;

    int large = 0; //괄호들 카운팅

    int middle = 0;

    int small = 0;

   

    //우선적으로 짝이 맞지 않는 괄호들은 계산이 필요없음 그냥 0임

    for(int i = 0; i < s.length();i++){

        if(s[i] == '(')

            small++;

        else if(s[i] == '[')

            middle++;

        else if(s[i] == '{')

            large++;

        else if (s[i] == ')')

            small--;

        else if (s[i] == ']')

            middle--;

        else if (s[i] == '}')

            large--;

    }

    if(small != 0 || middle != 0 || large != 0)

        return 0;

   

   

    for(int i = 0; i < s.length();i++){

        large = 0; //괄호들 카운팅

        middle = 0;

        small = 0;

        int is_correct = 1; //1이라면 answer++ 0이라면 변화x

       

        for(int j = 0;j < s.length();j++){

            if(s[j] == '(')

                small++;

            else if(s[j] == '[')

                middle++;

            else if(s[j] == '{')

                large++;

            else if (s[j] == ')')

                small--;

            else if (s[j] == ']')

                middle--;

            else if (s[j] == '}')

                large--;

            //반복문을 돌때 닫힌 괄호가 먼저 나오거나 많다는 것은 올바른 괄호 문자열이 아님.

            if(small < 0 || middle < 0 || large < 0){

                is_correct = 0;

                break;

            }

        }

        if(is_correct == 1)

            answer++;

       

        s.push_back(s[0]);

        s.erase(0,1);

    }

   

    return answer;

}

위와 같이 stack을 사용하지 않고 그냥 무지성으로 괄호에 대해서 ++ -- 를통해 갯수 체킹을 한 결과

테스트 14에서 너 틀렸어! 라는 결과를 얻게 되었습니다.

 

가만히 앉아 생각을 해보니 이런 문자열 문제는 ()하나만 있다면 몰라도 다른 것들이 점점 추가될수록 스택을 사용해야합니다.

 

고친 코드 (맞는 코드)

/*

잘못된 생각 그냥 stack으로 할껄 그랬다.

왜냐하면 [({)}] 이러한 형태로 ({)} 이렇게 되면 올바르지 않은 괄호이기디 때문에 스택으로 해서

스택을 푸시하는데 스택의 top과 지금 문자와 비교를 통해 진행을 하면 간단한데 괜히 시간 낭비했음

*/

#include <string>

#include <vector>

#include <stack>

using namespace std;

int solution(string s) {

    int answer = 0;

    int large = 0; //괄호들 카운팅

    int middle = 0;

    int small = 0;

   

    //우선적으로 짝이 맞지 않는 괄호들은 계산이 필요없음 그냥 0임

    for(int i = 0; i < s.length();i++){

        if(s[i] == '(')

            small++;

        else if(s[i] == '[')

            middle++;

        else if(s[i] == '{')

            large++;

        else if (s[i] == ')')

            small--;

        else if (s[i] == ']')

            middle--;

        else if (s[i] == '}')

            large--;

    }

    if(small != 0 || middle != 0 || large != 0)

        return 0;

   

    for (int j = 0 ; j <s.length(); j++){

        stack<char>stk;

       

        for(int i =0; i < s.length();i++){

            if(s[i] == '(' || s[i] == '{' || s[i] =='[')

                stk.push(s[i]);

            else{

                if(s[i] == ')' && stk.top() == '(')

                    stk.pop();

                else if(s[i] == '}' && stk.top() == '{')

                    stk.pop();

                else if(s[i] == ']' && stk.top() == '[')

                    stk.pop();

            }

        }

        if(stk.empty())

            answer++;

        s.push_back(s[0]);

        s.erase(0,1);

    }

    return answer;

}

이렇게 스택을 이용해 여는 괄호에 대해서는 stack에다가 push를 진행하고 닫는 괄호들이 있을때는 stack의 top과 비교를 통해 pop을 진행해주면 됩니다 :)