16890번 창업

https://www.acmicpc.net/problem/16890

어려웠다.

다시 한 번 풀어볼 문제이다.

나는 계속 오름차순, 내림차순 정렬을 하여

앞에서부터 순서대로 인덱스를 통해 각각 문자를 비교하여 출력하게 하였는데,

다른 사람의 코드과 도움을 받고 보니, 출력을 즉시하면 안 되었다.

위처럼 구현하면, 따져야할 경우의 수가 너무 많다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
char result[300010];
 
bool cmp(char a, char b)
{
    return a > b; // 내림차순
}
 
int main(void)
{
    string koo, cube;
 
    cin >> koo;
    sort(koo.begin(), koo.end());
 
    cin >> cube;
    sort(cube.begin(), cube.end(), cmp);
 
    int len = koo.length();
 
    int ks = 0, ke = (koo.length() + 1) / 2 - 1;
    int cs = 0, ce = cube.length() / 2 - 1;
 
    if (ke <= 0) ke = 0;
    if (ce <= 0) ce = 0;
 
    bool turn = true;
 
    int rs = 0, re = koo.length() - 1;
 
    for (int i = 0; i < len; i++)
    {
        if (turn)
        {
            if (koo[ks] < cube[cs]) result[rs++] = koo[ks++];    
            else result[re--] = koo[ke--];        
        }
        else
        {
            if (koo[ks] < cube[cs]) result[rs++] = cube[cs++];
            else result[re--] = cube[ce--];    
        }
 
        turn = !turn;
    }
 
    printf("%s\n", result);
 
    return 0;
}