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))
문제를 보면, 구사과는 가장 사전순으로 빠르게,
큐브러버는 사전순으로 느리게이다.
이때 그냥 생각해보면 정렬하고,
앞에서부터, 구사과는 작은걸
큐브러버는 큰걸 둔다고 생각을 하고 두면, 안된다.
이 문제는 최적의 방법이므로, 두사람의 패를 알고 있다고 가정을 하고 풀어야한다.
만약 구사과가 가진 문자열 중 가장 작은 것이, 큐브러버의 문자열중 가장 큰것보다, 작을때에는
작은걸 제일 앞에 두면 된다.
하지만 가장 작은것이 큐브러버 문자열 중 가장 큰것보다 크거나 같을때에는,
자신이 무조건 써야하는 패중에서 가장 큰걸 가장 뒤에 두는게 사전순으로 빠르게 하는방법이다.
이와 같이
큐브러버도 자신이 가진 문자열 중 가장 큰 것이, 구사과가 가진 가장 작은 문자열보다 클때에는
앞에 자신의 가장 큰 문자열을 위치시키면 된다.
하지만 구사과가 가진 작은 문자열보다 자신이 가진 가장 큰 문자열이 작을때에는
자신이 가진 가장 작은 문자열을 뒤로 보내는것이, 사전순으로 늦게 하는방법일것이다.
이런식으로 해서 문제를 풀면된다.
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ/백준] 2695 공 (0) | 2022.06.21 |
|---|---|
| [BOJ/백준] 3343 장미 (1) | 2022.05.11 |
| [BOJ/백준] 19566 수열의 구간 평균 (0) | 2022.01.15 |
| [BOJ/백준] 12912 트리 수정 (0) | 2021.12.23 |
| [BOJ/백준] 2240 자두나무 (0) | 2021.12.04 |
