[프로그래머스] - 괄호 회전하기(C/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

 

---

[문제 풀이]

문제에서 주어진 괄호들을 회전시켜서 올바르게 나열된 괄호의 횟수를 반환하면 된다.

올바르게 나열되었다는 것은

[]{}, [{}]와 같이 여는 괄호가 왼쪽, 닫는 괄호가 오른쪽에 있을때를 얘기한다.

][{}와 같이 닫는괄호가 먼저 나오게 된다면 그것은 올바르지 않은 괄호이다.

입력된 괄호들을 한개씩 회전시키면서 모든 괄호가 올바른괄호일때의 횟수를 저장하면 된다.

 

입출력 예에서 두번째 예제에 대해서 얘기하자면,

입력된 괄호의 나열이 되기 전까지 회전시키면서 확인하면 된다.

회전은 왼쪽으로 회전시키든, 오른쪽으로 회전시키든 결과는 같으므로 상관없다.

그 결과는 아래와 같다.

 

}]()[{        ->         x

]()[{}        ->         x

()[{}]        ->         o

)[{}](        ->         x

[{}]()        ->         o

{}]()[        ->         x

 

입력된 배열이 올바른 괄호인지 확인하기위해 반복문을 사용한다.

확인하는 방법은

1. vector가 비어있을때 },],)와 같이 닫는괄호가 입력된 경우는 확인할 필요가 없이 올바른 괄호가 아니므로 break

2. vector에 여는 괄호 {,[,( 가 입력되었을경우에 push한다.

3. vector의 마지막 괄호를 확인하고, 현재 넣으려고 하는 괄호와 매칭되는 괄호일경우 pop한다.

4. 반복문이 끝났을때, vector가 비어있다면 올바른 괄호이므로 answer 값을 증가시킨다.

 

회전시키는 방법은 깔끔하게 첫번째 인덱스의 괄호를 뒤에 넣고 첫번째 원소를 삭제하는 방법도 있지만,

예) }]()[{        ->         }]()[{} (맨뒤에  '}' 추가)        ->           ]()[{} (맨 앞에 '}' 삭제)

 

맨앞에 문자를 삭제하는것도 자원을 비용이라고 생각했다.

따라서 뒤에 추가하고 추가한만큼 인덱스를 증가시켜 확인하도록 코드를 작성했다.

예) }]()[{        ->         }]()[{} (맨뒤에  '}' 추가)        ->           }]()[{} (맨 앞에 }를 제외한 ]()[{}만 확인)  

인덱스만 잘 관리하면 되겠다고 생각했다.

 

위에서 올바른 괄호인지 확인하는 방식에서 vector가 비어있을때 answer를 증가시키는 방식으로 진행했다.

하지만,  1번에서 괄호가 비어있을때 닫는 괄호가 입력되었을 경우에 push하지 않고 break하게되면

vector가 비어있어 올바른 괄호라고 판단할수있다.

이때 bool 변수를 두어서 체크해도 되지만, 비어있을때 닫는 괄호가 입력된 경우 해당 괄호를 push하고 break하게 되면

비어있지 않으므로 올바른 괄호라고 체크되지 않는다.

 

꼭 모든 반복문에서 올바른 괄호를 체크하는 vector를 clear해주어야한다.

 

[코드]

[GitHub]

GitHub - EGyeom/ProblemSolving

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

#include <string>
#include <vector>

using namespace std;

int solution(string s) {
    int answer = 0;
    vector<char> v;
    int sSize = s.size();
    for(int j = 0 ; j < sSize; j++)
    {
        for(int i = j ; i < sSize + j; i++)
        {
            if(s[i] == '{' || s[i] == '[' || s[i] == '(')
            {
                v.push_back(s[i]);
            }
            else if(v.empty() == false)
            {
                if(v.back() == '{' && s[i] == '}')
                    v.pop_back();
                if(v.back() == '(' && s[i] == ')')
                    v.pop_back();
                if(v.back() == '[' && s[i] == ']')
                    v.pop_back();
            }
            else
            {
                v.push_back(s[i]);
                break;
            }
        }
        if(v.empty()) answer++;
        v.clear();
        s += s[j];
    }
    
    return answer;
}