[알고리즘 풀이 분석] 프로그래머스 괄호 회전하기

돌아오는 토요일 웍스모바일 코딩테스트가 잡혔다. nhn 2차 테스트를 준비하면서 CS 공부중이었는데,, 웍스 서류합이 떴고 시험 시간이 겹친다,, ㅜ 처음으로 웍스 서합했는데 둘중 하나를 포기 해야 한다니,, 금요일 내내 고민을 참 많이 했지만 iOS 업무를 경험해볼 수 있는 웍스에 도전해보려 한다,, 전환률이 걱정되지만 뭐 일단 붙고 보자!!!

고민고민 하면서 문자열 문제를 하나 풀어보았다. 간단한 문제지만 웍스에 문자열 구현과 같은 기본적인 문제가 자주 나온다길래 가볍게 하나 풀어보았다. 풀어본 문제는 프로그래머스 괄호 회전하기 이다.

프로그래머스 괄호 회전하기

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

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

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

입출력

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

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

나의 풀이

전형적인 괄호 확인 문제이고 문자열 길이 만큼 문자열을 회전 시킨다는 것만 추가된 형식이다. stack 을 이용해서 왼쪽 괄호라면 넣어주고 오른쪽 괄호라면 짝을 확인한다. 확인하는 과정에서 짝이 맞지 않으면 다음 회전으로 넘어간다.

채점 결과 13번 테스트 케이스에서만 통과하지 못했는데 이 부분은 모든 짝이 다 맞지만 stack 에 좌괄호 하나가 남아있는 경우를 체크하지 못해서 통과하지 못한 것 같았다.

문자열의 길이자체가 홀수일때는 어떠한 경우에도 짝이 맞지 않으므로 회전 시키기 전에 한번 확인해주는 코드를 넣어주니 통과하였다.

코드

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

using namespace std;

int solution(string s) {
    int answer = 0;
    int len = s.size(), rotate = 0;
    
    if(len%2 == 1) return 0;
    
    do{
        stack<string> st;
        bool correct = true;
        
        for(int i=0; i<s.size(); i++){
            string tok = s.substr(i,1);
            if(tok== "{" || tok== "(" || tok== "[") st.push(tok);
            else{
                if(st.empty()) {
                    correct = false;
                    break;
                }
                
                if((tok=="}"&&st.top()=="{") || (tok=="]"&&st.top()=="[") || (tok==")"&&st.top()=="(")){
                    st.pop();
                }else {
                    correct = false;
                    break;
                }
            }
        }
        
        if(correct) answer++;
        s = s.substr(1, len-1) + s.substr(0,1);
        rotate++;
        
    }while(rotate<len);
    
    
    return answer;
}