[백준/16890] 창업 (Python)

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

16890번: 창업

Status : Solved

Time : 01:40:13

 

---

 

문제 설명

 

구사과와 큐브러버는 공동 창업을 하려고 한다. 두 사람은 회사 이름을 아직 결정하지 못했고, 서로가 생각한 회사 이름이 상대방을 설득하지 못해 일을 시작하지 못하고 있었다. 더 이상 일정을 늦출 수 없는 두 사람은 게임을 통해 회사 이름을 정하기로 했다. 다행히도 두 사람은 회사 이름의 길이에 대한 의견이 일치하고, N개의 글자로 이루어져 있어야 한다.

두 사람은 각자 사용할 N개의 문자를 정했다. 같은 문자가 여러 번 포함되었을 수도 있다. 가장 처음에 회사의 이름은 물음표(?) N개이다. 이제, 서로 턴을 번갈아 가지면서 게임을 진행하려고 한다. 게임은 구사과가 먼저 시작한다.

각 턴이 되었을 때, 각 사람은 미리 정해놓은 문자 중 하나를 고르고, 물음표 하나를 고른 문자로 변경한다. 고른 문자는 더 이상 사용할 수 없다. 게임은 모든 물음표가 문자로 바뀌면 끝난다.

예를 들어, 정보를 좋아하는 구사과가 고른 문자가 [i, o, i] 이고, 수학을 좋아하는 큐브러버가 고른 문자가 [i, m, o]인 경우가 있다면, 게임은 다음과 같이 진행될 수 있다.

• 가장 처음에 회사 이름은 ???이다.
• 구사과가 두 번째 물음표를 i로 변경해 회사 이름을 ?i?로 변경한다. 이제 구사과의 고른 문자는 [i, o] 이다.
• 큐브러버가 세 번째 물음표를 o로 변경해 회사 이름을 ?io로 변경한다. 이제 큐브러버의 고른 문자는 [i, m] 이다.
• 마지막으로, 구사과가 첫 번째 물음표를 o로 변경해 회사 이름을 oio로 변경한다.
• 최종적으로 회사의 이름은 oio가 된다.

구사과는 회사 이름을 사전 순으로 가장 앞서게 만들고 싶어하고, 큐브러버는 회사 이름을 사전 순으로 가장 뒤에 오게 만들고 싶어한다.

두 사람이 게임을 최적의 방법으로 진행했을 때, 회사 이름이 무엇인지 알아내는 프로그램을 작성하시오.

 

입력 및 출력

 

입력

입력은 길이가 N(1 ≤ N ≤ 300,000)인 문자열 두 개로 이루어져 있다. 모든 문자열은 알파벳 소문자로만 이루어져 있다. 첫 번째 줄에 주어지는 문자열은 구사과가 고른 문자이고, 두 번째 줄에 주어지는 문자열은 큐브러버가 고른 문자이다.

 

출력

두 사람이 창업한 회사의 이름을 출력한다.

 

---

 

풀이

 

꽤 오래 걸린 문제인데, 처음의 단순한 접근법으로는 풀리지 않은터라 시간이 많이 소모되었다.

우선 두 문자열은 차례대로 오름차순 및 내림차순으로 정렬한 결과의 ( N - N // 2, N // 2 ) 개가 쓰이게 된다. 기본적으로 '사전 순'이라는 단서가 있으므로, 사전순 배열에 더 큰 영향을 미치는 문자열 앞쪽부터 번갈아 가며 채워나가게 된다. 따라서 일반적인 경우는 그 리스트의 가장 우선순위가 높은 문자를 결과값의 가장 앞선 위치에 배열하는 것이 전략이 된다.

문제는 다음과 같은 반례로 갈음할 수 있다. 입력으로 bb, aa를 받는 경우를 생각해 보자.

앞선 전략대로 배열을 채워나가면 '??' -> 'b?' -> 'ba'순이 된다. 하지만 맨 첫 번째 입장에서는 b 를 앞쪽 대신 뒤쪽에 배치하여 '??' -> '?b' -> 'ab'를 유도하는 것이 더 최적화된 전략이라고 볼 수 있다. 이러한 경우는 자신 리스트의 최선의 결과(idx == 0)가 상대 리스트의 최악의 결과(idx == 0)보다 더 우선순위가 낮을 때 발생한다. 이러한 경우는 무작정 앞쪽을 채워나가는 것보다, 자신 리스트의 최악의 결과를 결과값의 가장 뒤쪽 위치에 배열하는 전략을 써야 한다. 그래야지만 다음에 상대방이 어떤 전략을 세우던 자신이 결과값 앞쪽에 배열하는 것보다 더 나은 결과를 가져오게 된다.

 이 점을 제대로 정의내리지 못해 시간을 많이 썼던 것 같다.

 

from collections import deque

list1 = sorted(list(input().strip()))
list2 = sorted(list(input().strip()), reverse = True)
N = len(list1)

list1 = deque(list1[:N - N//2])
list2 = deque(list2[:N//2])
full_list = ['']*N
idx, rev_idx = 0, N-1
turn = 1

for _ in range(N) :
  cur_list = list1 if turn == 1 else list2

  if list1 and list2 and list1[0] >= list2[0] :
    full_list[rev_idx] = cur_list.pop()
    rev_idx -= 1
  else :
    full_list[idx] = cur_list.popleft()
    idx += 1
  
  turn = -turn

print(''.join(full_list))

풀이 완료!