[백준] 창업

문제 링크: https://www.acmicpc.net/problem/16890

16890번: 창업

 

1. 문제 이해

구사과와 큐브러버가 사명을 정하는데 구사과는 사전순으로 가장 앞서게 하고 싶고 큐브러버는 사전 순으로 늦게 나오도록 하고 싶다. 각자 고른 알파벳 문자 N개가 있고 구사과를 시작으로 하나씩 문자를 배치할 수 있다. 최종적으로 N개의 알파벳을 배치하여 나온 사명을 알아내는 것이 문제의 목표입니다.

2. 문제 접근

deque를 활용하는 게임 이론인 것까지는 접근했지만 deque에 들어가는 문자의 개수 제한을 두어야하는 부분을 알지 못해서 인터넷 검색을 통해 알게 되었습니다. 

 

먼저, 구사과는 사전 순으로 앞서고 싶기 때문에 최대한 사전 순으로 앞서는 문자가 앞에 배치하도록 하고 싶어하므로 오름차순으로 정렬해줍니다. 반대로 큐브러버의 경우에는 내림차순으로 정렬해줍니다. 다음으로는 정렬된 문자들을 deque에 넣어줍니다. 이때의 포인트는 각자 선택한 모든 문자를 사용하는 것이 아니므로 구사과는 먼저 시작하므로 앞에서부터 (N + 1) / 2개의 문자만 큐브러버의 경우 N / 2개의 문자만 deque에 넣어주면 됩니다.

 

다음으로 차례대로 각자 목표에 맞게 알파벳을 선택해주면 됩니다. 구사과는 자신이 가지고 있는 문자중 가장 앞서는 문자를 놓으려고 시도하는데 다음 큐브러버가 놓으려고 하는 문자와 비교합니다. 만약 구사과가 놓으려는 문자가 'a'이고 큐브러버가 놓으려는 문자가 'b'이면 놓을 수 있는 가장 왼쪽 자리에 두면 됩니다. 그런데 구사과가 놓으려는 문자가 'b'이고 다음 큐브러버가 놓으려는 문자가 'a'라면 자신이 가진 가장 늦게 나오는 문자를 놓을 수 있는 가장 오른쪽에 두어야합니다. 그 이유는 'b'라는 자신의 문자는 자신이 가진 가장 앞서나오는 문자인데 현재 큐브가 놓으려는 'a'는 큐브가 가진 가장 늦게 나온는 문자이므로 구사과가 가지고 있는 문자들보다 큐브가 가진 문자들이 더 앞선다는 것을 알 수 있습니다. 그렇기 때문에 자신이 가진 문자중 가장 늦게 나오는 문자를 오른쪽에 두어야하고 반대로 큐브의 턴에도 똑같은 방식이 적용됩니다.

3. 풀이

import sys
from collections import deque

sys.setrecursionlimit(3 * (10 ** 6))

sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

koo, cube = list(input().rstrip()), list(input().rstrip())

n = len(koo)

koo.sort()
cube.sort(reverse=True)

koo = deque(koo[:((n + 1) // 2)])
cube = deque(cube[:(n // 2)])
ans = ['?'] * n


#print(koo, cube)
def koo_turn(left, right, depth):
    global ans

    if depth >= n:
        return

    if cube and koo and koo[0] >= cube[0]:
       ans[right] = koo.pop()
       cube_turn(left, right - 1, depth + 1)
    else:
       ans[left] = koo.popleft()
       cube_turn(left + 1, right, depth + 1)

def cube_turn(left, right, depth):
    global ans

    if depth >= n:
        return

    if koo and cube and koo[0] >= cube[0]:
       ans[right] = cube.pop()
       koo_turn(left, right - 1, depth + 1)
    else:
       ans[left] = cube.popleft()
       koo_turn(left + 1, right, depth + 1)

koo_turn(0, n - 1, 0)

print(''.join(ans))

4. 회고

문제에 대한 접근 방식은 맞게 했지만 결국 사용되는 문자는 한정되어있다는 부분을 놓쳐서 검색해서 풀었던 문제.