[ SWEA 5672 ] 올해의 조련사 (C++)

SWExpertAcademy의 올해의 조련사(5672) 문제이다.

[ 문제풀이 ]

문제의 조건에 맞게 줄을 세우는 방법을 천천히 알아보자.

먼저, 문제에서 제시한 줄을 세우는 조건은 다음과 같다.

"기존의 줄과 새로운 줄, 두 줄을 세운 다음, 기존의 줄에서 가장 앞에 있는 앵무새, 가장 뒤에 있는 앵무새를 새로운 줄의 마지막에 세우는 것을 반복"

그렇다면 우리는 기존의 줄에서 '가장 앞에 있는 문자'와 '가장 뒤에 있는 문자'를 비교해주면서 새로운 줄을 세우면된다.

우리가 새로운 줄을 세울 때 고려해줘야 하는 것은 3가지 경우이다.

1. 현재 문자열에서 '가장 앞에있는 문자' 가 '가장 뒤에있는 문자' 보다 더 빠른 문자일 경우

2. 현재 문자열에서 '가장 뒤에있는 문자' 가 '가장 앞에있는 문자' 보다 더 빠른 문자일 경우

3. 현자 문자열에서 '가장 앞에있는 문자'와 '가장 뒤에있는 문자'가 같은 경우

1번과 2번의 경우는 당연히 더 빠른 문자가 앞에 오는 것이 유리하기 때문에, 그대로 새로운 줄에 추가를 해주면 된다.

간단하게 예제 Test Case로 주어진 [ A C D B C B ] 로 생각을 해보자.

현재 문자열에서 가장 앞에 있는 문자는 'A' 이고 가장 마지막에 있는 문자는 'B' 이다.

당연히, A가 B보다 더 빠른 문자이므로, 새로운 줄에 A를 세워주자.

그럼 새로운 줄 = [ A ] 가 되고, 기존의 문자열은 가장 앞에 'A'가 빠졌으니, [ C D B C B ] 의 형태로 남아있다고

생각해볼 수 있다.

이 후, 또 가장 앞에 있는 문자와 가장 뒤에있는 문자를 비교해보자.

C 와 B 이므로, 가장 뒤에 있는 문자인 'B'가 새로운 줄의 가장 마지막에 추가될 것이다.

새로운 줄 = [ A B ]

동시에, 기존의 문자열에서는 가장 마지막 문자인 'B'가 빠졌으므로 [ C D B C ] 의 형태로 남아있다고 생각해 볼 수 있다.

그 다음 문자 2개를 비교했더니, 'C'와 'C'로 같은 문자이다.

이 경우가 위에서 말한 3번 경우이다.

3번 경우일 때는 "어떤 문자를 선택하는 것이 더 유리할지" 에 대해서 생각을 해봐야 한다.

지금 남아있는 [ C D B C ] 에서는 무슨색 'C'를 선택하는 것이 더 유리할까 ??

아마, 빨간색 'C'를 선택하는 것이 더 유리하다고 볼 수 있다. 왜냐하면, 해당 'C'를 선택한 후의 그 다음 문자들을

비교해보게 되면, 'D'와 'B'인데, 'D'에 비해서 'B'가 더 빠른 문자이기 때문에, 조금이라도 더 빠른 문자열을 만들기

위해서는 상대적으로 더 빠른 문자인 'B'를 빠르게 선택해주는 것이 좋기 때문이다.

즉 ! 같은 문자가 나왔을 경우에는, 그 다음 문자들을 계속해서 탐색해 보면서 무슨 문자를 비교하는 것이 더 유리한지

판단해주면 된다.

이 경우에서 또 한가지 생각해봐야 할 것이 있다. 이런 경우를 생각해보자.

위에서 말한 [C D B C] 가 아닌, [C C C C]가 남아있다고 생각해보자.

이 경우에는, 그 다음 문자들을 비교한다고 하더라도, 무슨 문자를 뽑는 것이 더 유리한지 결론이 나오질 않는다.

왜냐하면 다 똑같은 문자들만 있기 때문이다. 사실 이 경우에는 "무슨 문자를 뽑든 상관이 없다" 라고 생각하면 된다.

따라서, 우리는 같은 문자가 나왔을 때 "어떤 문자를 선택하는 것이 더 유리한지 결정했습니다 or 결정하지 못했습니다"

를 알려줄만한 변수를 생성해서 체크를 해줘야 한다.

어떤 문자를 선택하는 것이 더 유리한지 결정 했다면, 해당 문자를 선택하면 되는 것이고, 그게 아니라면, 아무문자나

선택해도 상관이 없다 !

위에서 설명하는 과정에서 [ A B C D B C ] 가 있을 때, A를 선택했으면 [ B C D B C ] 의 형태로 남아있다 ~~

라는 식으로 이야기를 했는데, 실제 구현에서는 해당 문자를 삭제한 것은 아니고, 2개의 변수를 만들어서 투포인터 개념으로

관리해 주었다.

문자열의 왼쪽을 나타내는 변수1 과 오른쪽을 나타내는 변수2를 만들어서, 왼쪽이 더 작다면, 변수1++, 오른쪽이 더 작다면,

변수2-- 이런식으로 간단하게 표현했다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<string>
 
#define endl "\n"
#define MAX 2000
using namespace std;
 
int N;
char Name[MAX];
vector<char> Answer;
 
char Min(char A, char B) { if (A < B) return A; return B; }
 
void Initialize()
{
    Answer.clear();
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++) cin >> Name[i];
}
 
void Solution()
{
    int Left = 0;
    int Right = N - 1;
    int Same_Cnt = 0;
    
    for (int i = 0; i < N; i++)
    {
        if (Name[Left] < Name[Right]) Answer.push_back(Name[Left++]);
        else if (Name[Right] < Name[Left]) Answer.push_back(Name[Right--]);
        else
        {
            int Iter_Left = Left + 1;
            int Iter_Right = Right - 1;
            bool Flag = false;
 
            while (Iter_Left < Iter_Right)
            {
                if (Name[Iter_Left] < Name[Iter_Right])
                {
                    Answer.push_back(Name[Left++]);
                    Flag = true;
                    break;
                }
                else if (Name[Iter_Right] < Name[Iter_Left])
                {
                    Answer.push_back(Name[Right--]);
                    Flag = true;
                    break;
                }
                Iter_Left++;
                Iter_Right--;
            }
 
            if (Flag == false) Answer.push_back(Name[Left++]);
        }
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " ";
        for (int i = 0; i < Answer.size(); i++) cout << Answer[i];
        cout << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}