[백준] 16890번 창업

16890번: 창업

구사과는 사전 순으로 가장 앞서게 만들고 싶어 하므로

오름차순 정렬한다.

큐브러버는 사전 순으로 가장 뒤에 오게 만들고 싶어 하므로

내림차순 정렬한다.

 

회사의 이름은 N개의 문자열로 이루어져 있고

고르는 순서는 항상 구사과가 먼저이므로

구사과 문자열에서 (N+1)/2개,

큐브러버 문자열에서 N/2개

를 골라야 한다.

 

ex)

koooosaga → aagkoooos

cubelover → vuroleecb

 

1번째 - 구사과 차례

aagko 에서 제일 작은 문자가

vuro 에서 제일 큰 문자보다 작으면

aagko 에서 제일 작은 문자가 최대한 앞으로 가야 한다.

a

 

2번째 - 큐브러버 차례

vuro 에서 제일 큰 문자가

agko 에서 제일 작은 문자보다 크면

vuro 에서 제일 큰 문자가 최대한 앞으로 가야 한다.

a

v

 

3번째 - 구사과 차례

agko 에서 제일 작은 문자가

uro 에서 제일 큰 문자보다 작으면

agko 에서 제일 작은 문자가 최대한 앞으로 가야 한다.

a

v

a

 

4번째 - 큐브러버 차례

uro 에서 제일 큰 문자가

gko 에서 제일 작은 문자보다 크면

uro 에서 제일 큰 문자가 최대한 앞으로 가야 한다.

a

v

a

u

 

이런 식으로 표를 끝까지 채우면 이렇게 된다.

a

v

a

u

g

r

k

o

o

 

 

zzzz → zzzz

aaaa →aaaa 

인 경우는 어떨까?

 

1번째 - 구사과 차례

zz 에서 제일 작은 문자가

aa 에서 제일 큰 문자보다 크거나 같다면

zz 에서 제일 큰 문자가 최대한 뒤로 가야 한다.

z

 

2번째 - 큐브러버 차례

aa 에서 제일 큰 문자가

z 에서 제일 작은 문자보다 작거나 같다면

aa 에서 제일 작은 문자가 최대한 뒤로 가야 한다.

a

z

 

이런 식으로 표를 채우면 이렇게 된다.

a

z

a

z

 

 

구사과의 입장에서는

작은 문자가 앞으로 갈수록 좋은데

 

만약 자기가 가지고 있는 제일 작은 문자가

큐브러버가 가지고 있는 제일 큰 문자보다 크거나 같다면

자기가 가지고 있는 제일 큰 문자가 뒤로 갈수록 좋다.

 

큐브러버 입장에서는

큰 문자가 앞으로 갈수록 좋은데

 

만약 자기가 가지고 있는 제일 큰 문자가

구사과가 가지고 있는 제일 작은 문자보다 작거나 같다면

자기가 가지고 있는 제일 작은 문자가 뒤로 갈수록 좋다.

 

이 포인트를 파악하여 구현해주어야 한다.

#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <deque>
using namespace std;
string a, b, front, back;
deque <char> A, B;

int main() {
	cin >> a >> b;
	sort(a.begin(), a.end());
	sort(b.begin(), b.end(), greater<>());

	for (int i = 0; i < (int)(a.size() + 1) / 2; i++) A.push_back(a[i]); // 오름차순
	for (int i = 0; i < b.size() / 2; i++) B.push_back(b[i]); // 내림차순

	for (int i = 0; i < a.size(); i++) {
		if (i % 2) { // 큐브러버 차례
			if (A.empty() || A.front() < B.front()) front += B.front(), B.pop_front(); // 큐브러버의 제일 큰 애가 구사과의 제일 작은 애보다 크면 앞으로 가는게 좋다
			else back += B.back(), B.pop_back();
		}
		else { // 구사과 차례
			if (B.empty() || A.front() < B.front()) front += A.front(), A.pop_front(); // 구사과의 제일 작은 애가 큐브러버의 제일 큰 애보다 작으면 앞으로 가는게 좋다
			else back += A.back(), A.pop_back();
		}
	}

	reverse(back.begin(), back.end());
	cout << front << back;
	return 0;
}