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

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

코딩테스트 연습 - 괄호 회전하기

---

 

-풀이-

나는 먼저 스택을 사용했다.

1. 괄호 문자열을 탐색하며 여는 괄호 ( '(' , '{' , '[' ) 를 만나면 스택에 push해준다.

2. 닫힌 괄호를 만난다면 pop을 해준다. 이때 닫힌괄호를 만나 pop을 해주어야하는데 stack이 비어있다면, 이 괄호 문자열은 잘못된 문자열이다.

3. pop을 해준 열린 괄호와 현재 닫힌괄호를 비교해서 다른종류의 괄호라면, 잘못된 문자열이다.

4. 1~3번을 반복해주며 문자열 끝까지 왔는데, stack안에 괄호가 들어있다면, 잘못된 문자열이다.

5. 1~4번까지 잘 통과했다면 올바른 괄호 문자열이다.

 

이는 가장 최근에 만난 열린 괄호와 가장 최근에만난 닫힌 괄호의 종류가 같아야 식이 성립하는것을 이용한것이다.

 

이 함수를 문자열을 돌려가며 실행해주어, 올바른 괄호 문자열이면 answer++를해주면 된다.

 

-시간복잡도-

올바른 문자열인지 확인하는 함수는, 문자열 s의 길이만큼 탐색하며 수행하기 때문에 s의 길이를 N이라고 하면 O(N)이 된다.

이를 문자열 S를 N번 회전시키며 수행하므로 , 최종 시간복잡도는 O(N²)이 된다

 

-코드-

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

int change(char a){
    if(a=='('||a==')'){
        return 1;
    }
    else if(a=='{'||a=='}'){
        return 2;
    }
    else{
        return 3;
    }
}

bool check(string s){
    stack<char> st;
    for(int i=0;i<s.size();i++){
        if(s[i]=='['||s[i]=='('||s[i]=='{'){
            st.push(s[i]);
        }
        else{
            if(st.empty()){
                return false;
            }
            char tp=st.top();
            st.pop();
            if(change(tp)!=change(s[i])){
                return false;
            }
        }
    }
    if(st.size()){
        return false;
    }
    else{
        return true;
    }
}

int solution(string s) {
    int answer = 0;
    int sz=s.size();
    for(int i=0;i<sz;i++){
        if(check(s)){
            answer++;
        }
        s=s.substr(1,sz-1)+ s.substr(0,1);
    }
    return answer;
}