[ 프로그래머스 [ 월간코드챌린지 ] 괄호 회전하기 ] (C++)

프로그래머스의 괄호 회전하기(월간 코드 챌린지) 문제이다.

[ 문제풀이 ]

주어지는 괄호로 이루어진 문자열을 0칸 ~ 문자열의 길이칸 만큼 회전시켰을 때, 올바른 괄호 문자열이 몇 개가 있는지 구해야 하는 문제이다. 같은 괄호를 판단하기 위해 필요한 과정들부터 정답을 도출하는 과정까지 진행해보자.

 

#1. 답이 정해져 있는 Case.

가장 먼저 ! 탐색을 해보기도 전에 우리는 이미 특정 Case에 대해서는 정답을 한 눈에 바로 알아챌 수가 있다.

어떤 경우일까 ?? 바로, "주어진 문자열의 길이가 홀수인 경우" 이다.

문자열의 길이가 홀수인 경우에 어떻게 정답을 바로 알 수 있을까 ?? 생각을 해보면, 문자열의 길이가 홀수로 주어진 경우, 절대로 올바른 괄호로 이루어진 문자열이 될 수가 없다. 왜냐하면 ! 올바른 괄호로 이루어지기 위해서는 최소한 여는 괄호의 수와 닫는 괄호의 수가 동일해야 할 것이다. 예를 들어서 여는 괄호가(어떤 괄호든 종류에 상관없이) 1개 있다면, 올바른 문자열이 되기 위해서는 최소 닫는 괄호도 1개는 있어야 할 것이다.

즉 ! 올바른 괄호로 이루어진 문자열이 되기 위해서라면, 최소한 문자열의 길이가 짝수로만 이루어져 있어야 한다는 것이다.

절대로 홀수로 이루어져 있는 문자열을 어떻게 회전한다 하더라도, 절대로 올바른 괄호를 가진 문자열이 될 수가 없다.

문자열의 길이가 홀수인 경우, 반드시 정답은 0이 된다.

 

#2. 같은 괄호쌍 만들기

이제부터 본격적인 풀이에 들어가보자. 본인은 먼저 같은 괄호들을 숫자로 매핑시켜 주었다.

여기서 '같은 괄호' 라는 것은 여는 괄호와 닫는 괄호를 의미한다.

즉 ! '(' 와 ')' 를 같은 숫자로 매핑시켜 주었고, '{' 와 '}' 를 같은 숫자로 매핑시켜 주었고, '['와 ']'를 같은 숫자로 매핑시켜 주었다. 물론 이러한 과정 없이 탐색을 할때, 직접 조건문으로 구현을 하더라도 전혀 상관이 없다.

본인은 자료구조 map을 이용해서 위의 문자들을 같은 숫자들로 매핑을 시켜 주었다.

void Mapping(map<char, int> &MAP)
{
	MAP['('] = 1;
	MAP[')'] = 1;
	MAP['{'] = 2;
	MAP['}'] = 2;
	MAP['['] = 3;
	MAP[']'] = 3;
}

 

#3. 회전 시키기

우리는 주어진 문자열을 0번 부터 문자열의 길이 - 1번 까지 회전을 시켜야 한다.

그럼, 이해하기 쉽게 주어진 문자열이 ABCDE 라고 가정 해보자.

위의 문자열을 0번 회전할 경우 "ABCDE" 가 될 것이다.

위의 문자열을 1번 회전할 경우 "BCDEA" 가 될 것이다.

위의 문자열을 2번 회전할 경우 "CDEAB" 가 될 것이다.

위의 문자열을 3번 회전할 경우 "DEABC" 가 될 것이다.

위의 문자열을 4번 회전할 경우 "EABCD" 가 될 것이다.

그럼 위의 문자열들을 보면서 특징을 한번 찾아보자. 일단 회전할 때 마다, 가장 앞에 있는 문자들이 가장 뒤로 간다는 것을 알 수 있다. 그런데 ! 문자열을 원래의 문자열에서만 보려고 하지 말고, 이미 회전한 결과에서 한번 살펴보자.

0번 회전했을 때 "ABCDE" 가 되었다.

여기서 이미 회전한 결과인 "ABCDE"에서 1번 회전한 결과인 "BCDEA"가 되려면 어떻게 하면 될까 ??

단순하게, 가장 앞에 있는 문자를 가장 뒤로 보내주기만 하면 된다.

이어서, 1번 회전한 결과인 "BCDEA"에서 2번 회전한 결과인 "CDEAB"가 되려면 어떻게 하면 될까 ??

이 또한, 가장 앞에 있는 문자를 가장 뒤로 보내주기만 하면 된다.

즉 ! "K번 회전한 문자열을 구하기 위해서는, K - 1번 회전한 문자열에서 가장 앞에 있는 문자를 가장 뒤로 보내주기만 하면 된다." 라는 것을 알 수 있다. 이를 코드로 구현하면 다음과 같다.

string Rotate(string Str)
{
	string R_Str = Str;
	R_Str += Str[0];
	return R_Str.substr(1);
}

주어진 매개변수 "Str"은 "기존에 회전한 결과가 저장되어 있는 문자열"을 의미한다.

R_Str은 우리가 구하고자 하는 문자열인데, R_Str은 Str에다가, 가장 앞에 있는 문자만 추가한 문자열이 된다.

여기까지의 과정만 보면, Str = "ABCDE" 일 때, R_Str = "ABCDEA"가 될 것이다.

하지만 우리가 구하고자 하는 문자열은 "BCDEA" 이므로, 가장 앞에 있는 문자 하나를 짤라주어야 한다.

이를, substr() 함수를 통해서 문자열을 짤라낸 후에 return 시켜주는 방식으로 구현하였다.

String.substr(K) = String을 K번 인덱스부터 문자열의 마지막까지 짤라낸다.

 

#4. 올바른 문자열 확인하기

이제 최종적으로 정답을 도출하는데 가장 중요한 단계인, 올바른 문자열인지 확인하는 방법에 대해서 알아보자.

지금부터 '(' , '{' , '[' 는 "여는 괄호" 라고 표현할 것이고, ')' , '}' , ']' "닫는 괄호" 라고 표현할 것이다.

올바른 괄호인지 판단할 때 본인이 가장 중요하게 생각한 것은 "가장 최근에 나온 여는 괄호" 이다.

2가지 예시를 한번 살펴보자.

1. ")(" : 여는 괄호가 나오기도 전에 닫는 괄호가 나와버렸다. 즉 ! 이 경우는 "가장 최근에 나온 여는 괄호가 없는 상황 일 때, 닫는 괄호가 나와버린 상황" 이 된다.

2. "{ [ } ]" : 이도 잘못된 괄호 문자열이 된다. 잘못된 문자열인 이유는 다음과 같다.

"{ [ } ]" 이 문자열에서 파랑색 닫는괄호를 탐색하는 시점에서 생각을 해보자. 파랑색 닫는 괄호를 탐색하는 시점에서 "가장 최근에 나온 여는 괄호"는 빨강색으로 표시된 여는 괄호이다.

즉 ! 파랑색 괄호와 빨강색 괄호가 서로 같은 괄호가 아니기 때문에 이 또한 잘못된 문자열이 된다는 것을 의미한다.

따라서, 우리는 탐색을 함에 있어서 "가장 최근에 나온 여는 괄호" 에 대한 정보를 계속해서 저장해 주어야 한다.

 

그럼, 이와 같은 케이스를 한번 살펴보자.

"( [ ] )" 이와 같은 경우를 보자.

"( [ ] )" 이 문자열을 쉽게 이야기하기 위해서 가장 앞에 있는 문자부터 순서대로 A, B, C, D번 문자라고 표현하겠다.

A = '('  , B = '[' , C = ']' , D = ')' 가 되는 것이다.

C번 괄호를 확인할 때, 가장 최근에 나온 여는 괄호는 B가 될 것이다. 따라서 여기까지는 문제가 없다.

그런데 ! D번 괄호를 확인할 때를 살펴보자. D번 괄호를 확인하는 시점에서는, 가장 최근에 나오는 괄호가 B괄호이니까 이 문자열은 잘못된 문자열일까 ?? 그렇지 않다. 이 문자열은 올바른 문자열이다. 왜 그렇게 될까 ??

가장 최근에 나온 괄호가 B였지만, 사실 이 B번 괄호는 C번 괄호를 만나서, 즉, 올바른 쌍을 만나서 지워지게 된다.

따라서 실질적으로 남아있는 가장 최근에 나온 여는 괄호는 A가 된다. A와 D는 같은 쌍이기 때문에 또 만나서 지워지게 된다.

위의 예시에서 알 수 있듯이, 우리는 "가장 최근에 나온 여는 괄호를 순차적으로 알고 있어야 할 필요"가 있다.

본인은 이를 위해서 자료구조 'Stack' 을 사용해 주었다.

Stack은 LIFO(Last In First Out) 구조를 가진 자료구조로써, 가장 마지막에 들어간 데이터가 가장 먼저 나오게 된다.

이는, 상대적으로 먼저 들어간 데이터 입장에서는 나중에 나오게 된다는 것이다.

위에서 진행했던 "( [ ] )" 에서 Stack은 다음과 같이 작동할 것이다.

가장 처음에 A번 괄호를 만나서 Stack에 [ A ] 가 쌓이게 될 것이다.

이 후, B번 괄호를 만나서 Stack에 [ A B ] 가 쌓이게 될 것이다.

(편의상, 뒤쪽으로 갈 수록 Stack의 마지막에 쌓인 데이터라 가정하겠습니다.)

이 떄, C번 괄호를 만나게 되면 닫는 괄호이므로, 가장 최근에 나온 여는 괄호를 찾을 것이고, 이 괄호를 우리는 Stack의 top()에서 가져오게 될 것이다. top()를 가져오게 되면, 'B'가 나올 것이고 B와 C는 같은 괄호이므로 상쇄되어 없어질 것이다. 그렇게 되면, Stack에는 [ A ]만 남게 될 것이다. 이 상태에서, D번 괄호를 만나게 되면, 또 가장 최근에 나온 여는 괄호를 확인하기 위해서 Stack의 top()에 있는 'A'를 가져오게 될 것이고, 서로 같은 괄호이므로 상쇄되어 없어지게 될 것이다.

1. Stack을 통해서 "여는 괄호"들을 관리할 것이다.

2. "닫는 괄호"를 만나게 되면, Stack의 top()에 있는 "여는괄호"를 가져오고 비교할 것이다.

 

마지막으로 이 경우를 한번 더 살펴보자.

" [ { ( ) } ] ( "

위에서 이야기한 것과 같이 Stack을 통해서 진행해보자.

지금부터는 '( , )' 는 '1번괄호'로, '{ , }' 는 '2번괄호'로, '[ , ]'는 '3번괄호' 로 표현하겠다.

1. ' [ ' 는 여는 괄호이므로 Stack에 삽입. Stack = [ 3 ]

2. ' { ' 는 여는 괄호이므로 Stack에 삽입. Stack = [ 3 2 ]

3. ' ( ' 는 여는 괄호이므로 Stack에 삽입. Stack = [ 3 2 1 ]

4. ' ) ' 는 닫는 괄호이므로 가장 최근에 나온 괄호, 즉, Stack의 top()에 있는 괄호와 비교했을 때, 같은 괄호가 된다.

   Stack에서 '(' 가 빠지게 되어 Stack의 상태 = [ 3 2 ] 가 된다.

5. ' } ' 는 마찬가지로 올바른 괄호가 된다. Stack의 상태 = [ 3 ]

6. ' ] ' 는 마찬가지로 올바른 괄호가 된다. Stack의 상태 = [ ]

7. ' ( ' 는 여는 괄호이므로 Stack에 삽입. Stack = [ 1 ]

이렇게 되면 모든 문자열을 다 탐색을 했으므로 탐색이 종료되어 진다.

그런데 여기서 이상하다는 것을 느낄 수 있다. 단 한번도, 올바른 괄호쌍이 아니였던 적이 없지만, 우리는 이를 잘못된 문자열이라고 판단을 해야 한다.

바로 ! 모든 탐색이 끝난 후, Stack이 비어있어야만 올바른 문자열이라는 것이다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <map>
#include <stack>
using namespace std;
 
void Mapping(map<char, int> &MAP)
{
    MAP['('] = 1;
    MAP[')'] = 1;
    MAP['{'] = 2;
    MAP['}'] = 2;
    MAP['['] = 3;
    MAP[']'] = 3;
}
 
bool Check(string Str, map<char, int> GwalHo)
{
    stack<int> Stack;
    for (int i = 0; i < Str.length(); i++)
    {
        if (Str[i] == '(' || Str[i] == '{' || Str[i] == '[') Stack.push(GwalHo[Str[i]]);
        else
        {
            if (Stack.empty() == true) return false;
            if (Stack.top() != GwalHo[Str[i]]) return false;
            Stack.pop();
        }
    }
    if (Stack.empty() == true) return true;
    return false;
}
 
string Rotate(string Str)
{
    string R_Str = Str;
    R_Str += Str[0];
    return R_Str.substr(1);
}
 
int solution(string s) 
{
    if (s.length() % 2 != 0) return 0;
 
    map<char, int> GwalHo;
    Mapping(GwalHo);
    int answer = 0;
    if (Check(s, GwalHo) == true) answer++;
    string Str = s;
    for (int i = 1; i < s.length(); i++)
    {
        Str = Rotate(Str);
        if (Check(Str, GwalHo) == true) answer++;
    }
    return answer;
}