[2016 국민대 교내 경시대회] E. 카드 문자열

BOJ 13417 카드 문자열 (https://www.acmicpc.net/problem/13417)

이 문제는 한 면에 문자가 써 있는 카드를 왼쪽부터 하나씩 가져와 재배열하는데, 재배열한 카드들의 왼쪽 끝과 오른쪽 끝에만 카드를 놓을 수 있는 경우 사전순으로 가장 빠른 문자열이 되도록 재배열하는 문제입니다. 이 문제는 각각의 카드를 재배열할 때, 왼쪽 끝에 놓을 것인지 오른쪽 끝에 놓을 것인지를 판가름하는 기준이 무엇일지만 알면 쉽게 풀 수 있습니다. 

예제로 나와있는 M,K,U에 대해 생각해 보겠습니다.

M은 첫 번째 카드이므로 그냥 올려놓은 후, K를 추가할 때의 상황입니다. K를 M의 왼쪽에 올려놓아야 할까요 아니면 오른쪽에 올려놓아야 할까요? 

답은 왼쪽입니다. 이유는 왼쪽에 올려놓는 경우와 오른쪽에 올려놓는 각각의 경우, 사전상의 순서를 결정하는 알파벳은 누가 될 지에 대해 생각해보면 알 수 있습니다.

① 왼쪽에 올려놓는 경우 -> 새로 추가한 카드(K)

② 오른쪽에 올려놓는 경우 -> 기존에 가장 왼쪽에 있던 카드(M)

위와 같이 되기 때문에, 사전상의 순서를 결정하는 알파벳이 K가 되도록 하기 위해 왼쪽에 올려놓아야 합니다. 

그렇다면, 새로 추가한 카드와 기존에 가장 왼쪽에 있던 카드의 사전상의 순서가 같은 경우엔 사전상의 순서를 결정하는 알파벳은 누가 될까요? 만약 입력으로 B,A,C,A,B,A,C가 들어온다고 해보겠습니다. 세 번째 카드인 C까지 위의 규칙에 따라 재배열하면 A B C 가 되겠죠? 그런데, 네 번째 카드인 A를 추가하려고 할 때 문제가 발생합니다. 가장 왼쪽에 있는 카드인 A와 추가하려는 카드는 A의 사전상 순서가 같기 때문에, 가장 왼쪽에 있는 카드만 봐서는 A를 왼쪽에 놓을 지 오른쪽에 놓을 지 결정할 수 없기 때문입니다. 따라서, 추가하려는 카드 A와 처음으로 다른 카드가 사전상의 순서를 결정하는 알파벳이 됩니다. 아래의 그림을 보면 위의 예시의 경우, 처음으로 다른 카드인 B가 사전상의 순서를 결정하는 알파벳이므로 A보다 사전상의 순서가 늦어 A를 왼쪽에 올려놓아야 한다는 것을 알 수 있습니다.

#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
#include <math.h>
#include <stdlib.h>
#include <string.h>
 
using namespace std;
 
char ans[2001];
int N;
int l=1001, r=1001;
 
//카드를 왼쪽에 올려놓는 경우
void pushLeft(char alpha)
{
    l--;
    ans[l] = alpha;
}
 
//카드를 오른쪽에 올려놓는 경우
void pushRight(char alpha)
{
    r++;
    ans[r] = alpha;
}
 
int main()
{
    int T; scanf("%d", &T);
 
 
    while(T--)
    {
        //카드가 최대 1000장이므로 모두 왼쪽이나 오른쪽에 올려놓는 경우를 고려하기 위해
        //1001번째 칸부터 카드를 놓기 시작함
        l=1001; r=1001;
 
        int N; scanf("%d", &N);
        char now; cin >> now;
 
        ans[l] = now;
 
        for(int i=1; i<N; i++)
        {
            cin >> now;
 
            if(ans[l] > now)
                pushLeft(now);
            else if(ans[l] < now)
                pushRight(now);
            else
            {
                bool flag = false;
                for(int j=l; j<=r; j++)
                {
                    if(ans[j] != now)
                    {
                        if(ans[j] > now)
                            pushLeft(now);
                        else
                            pushRight(now);
 
                        flag = true;
                        break;
                    }
                }
                //이미 올려져있는 모든 카드가 지금 추가하려는 카드와 같은 카드인 경우
                //Ex) C C C C 인 상태에서 C카드를 추가하려는 경우, 왼쪽에 올려놓든 오른쪽에 올려놓든 상관없음
                if(!flag)
                    pushLeft(now);
            }
        }
 
        for(int i=l; i<=r; i++)
            printf("%c", ans[i]);
 
        printf("\n");
    }
}