[Programmers Level2] 괄호 회전하기(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

 

 

[입출력 예 설명]

 

 

입출력 예 #1

 

• 다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.

 

x	s를 왼쪽으로 x칸 만큼 회전	올바른 괄호 문자열?
0	"[](){}"	O
1	"](){}["	X
2	"(){}[]"	O
3	"){}[]("	X
4	"{}[]()"	O
5	"}[](){"	X

• 올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

 

입출력 예 #2

 

• 다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.

 

x	s를 왼쪽으로 x만큼 회전	올바른 괄호 문자열?
0	"}]()[{"	X
1	"]()[{}"	X
2	"()[{}]"	O
3	")[{}]("	X
4	"[{}]()"	O
5	"{}]()["	X

• 올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

 

입출력 예 #3

 

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

 

입출력 예 #4

 

• s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

 

 

[문제 풀이]

 

 

우선 대,중,소괄호가 포함되어 있는 문자열을 왼쪽으로 회전시킨다는 조건 때문에,

문자열을 char자료형 deque(덱)에 담았다.

 

그리고 올바른 괄호인지 판단하기 위해 isCorrect 함수를 만들었다.

올바른 괄호인지 판단할때는 스택을 사용했다.

 

• '(' 또는 '[' 또는 '{' 값(여는 괄호) 일 때는 스택에 push
• 스택이 비어있지 않고, 스택의 top이 '('(여는 괄호) 일 때 ')'(닫는 괄호)이 들어온다면 짝이 맞으므로 pop
• 스택이 비어있지 않고, 스택의 top이 '['(여는 괄호) 일 때 ']'(닫는 괄호)이 들어온다면 짝이 맞으므로 pop
• 스택이 비어있지 않고, 스택의 top이 '{'(여는 괄호) 일 때 '}'(닫는 괄호)이 들어온다면 짝이 맞으므로 pop
• 스택이 비어있고 ')' 또는 ']' 또는 '}' 값(닫는 괄호)일 때 스택에 push

 

그래서 최종적으로

스택이 비어있다면 올바른 괄호라고 판단을 하고

스택이 비어있지 않다면 올바른 괄호가 아니라고 판단을 했다.

 

그리고 회전시키기 위해 rotationDeque 함수를 만들었다.

deque을 참조자 형식으로 넘기고

함수 내부에서 deque(덱)의 front를 push_back해서 넣고, deque(덱)의 front를 pop_front를 해서 제거했다.

 

[C++ 스택] Stack 기본 사용법

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/Programmers: Study Programmers for Coding Test

 

 

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


using namespace std;

bool isCorrect(deque<char> d) {
    stack<char> fullstack; // 소,중,대 괄호 모두 포함

    int len = d.size();

    for(int i = 0; i < len; ++i) {
        if(d[i] == '{') {
            fullstack.push(d[i]);
        } else if(d[i] == '}') {
            if(!fullstack.empty()) {
                if(fullstack.top() == '{') {
                    fullstack.pop();
                }
            } else {
                fullstack.push(d[i]);
            }
        } else if(d[i] == '[') {
            fullstack.push(d[i]);
        } else if(d[i] == ']') {
            if(!fullstack.empty()) {
                if(fullstack.top() == '[') {
                    fullstack.pop();
                }
            } else {
                fullstack.push(d[i]);
            }
        }
        else if(d[i] == '(') {
            fullstack.push(d[i]);
        } else if(d[i] == ')') {
            if(!fullstack.empty()) {
                if(fullstack.top() == '(') {
                    fullstack.pop();
                }
            } else {
                fullstack.push(d[i]);
            }
        } else {
            // nothing
        }
    }

    if(!fullstack.empty()) {
        return false;
    } else {
        return true;
    }

}

void rotationDeque(deque<char>& d) {
    d.push_back(d.front());
    d.pop_front();
}

int solution(string s) {
    int answer = 0;
    int len = s.length();
    deque<char> dq;
    for(int i = 0; i < len; ++i) {
        dq.push_back(s[i]);
    }

    while(len != 0) {
        if(isCorrect(dq)) {
            ++answer;
        }
        rotationDeque(dq);
        --len;
    }

    
    return answer;
}