[BOJ/백준] 16890 창업

import sys
from collections import deque

def input():
    return sys.stdin.readline().rstrip()
A = list(input())

B = list(input())
N = len(A)

A.sort()
B.sort()
A = deque(A[:(N+1)//2])
B = deque(B[N-N//2:N])
answer = ['?']*N
left = 0
right = N-1

for idx in range(N):
    if idx%2:
        if A and A[0] >= B[-1]:
            answer[right] = B.popleft()
            right -= 1
        else:
            answer[left] = B.pop()
            left += 1
    else:
        if B and B[-1] <= A[0]:
            answer[right] = A.pop()
            right -= 1
        else:
            answer[left] = A.popleft()
            left += 1


print(''.join(answer))

 

문제를 보면, 구사과는 가장 사전순으로 빠르게,

 

큐브러버는 사전순으로 느리게이다.

 

이때 그냥 생각해보면 정렬하고, 

 

앞에서부터, 구사과는 작은걸

 

큐브러버는 큰걸 둔다고 생각을 하고 두면, 안된다.

 

이 문제는 최적의 방법이므로, 두사람의 패를 알고 있다고 가정을 하고 풀어야한다.

 

만약 구사과가 가진 문자열 중 가장 작은 것이, 큐브러버의 문자열중 가장 큰것보다, 작을때에는

 

작은걸 제일 앞에 두면 된다.

 

하지만 가장 작은것이 큐브러버 문자열 중 가장 큰것보다 크거나 같을때에는,

 

자신이 무조건 써야하는 패중에서 가장 큰걸 가장 뒤에 두는게 사전순으로 빠르게 하는방법이다.

 

이와 같이

 

큐브러버도 자신이 가진 문자열 중 가장 큰 것이, 구사과가 가진 가장 작은 문자열보다 클때에는 

 

앞에 자신의 가장 큰 문자열을 위치시키면 된다.

 

하지만 구사과가 가진 작은 문자열보다 자신이 가진 가장 큰 문자열이 작을때에는

 

자신이 가진 가장 작은 문자열을 뒤로 보내는것이, 사전순으로 늦게 하는방법일것이다.

 

이런식으로 해서 문제를 풀면된다.