BOJ_16890_창업 (Java)

[Gold I] 창업 - 16890

문제 링크

성능 요약

메모리: 47068 KB, 시간: 1076 ms

분류

그리디 알고리즘, 문자열, 정렬, 게임 이론

제출 일자

2025년 7월 8일 16:47:38

문제 설명

구사과와 큐브러버는 공동 창업을 하려고 한다. 두 사람은 회사 이름을 아직 결정하지 못했고, 서로가 생각한 회사 이름이 상대방을 설득하지 못해 일을 시작하지 못하고 있었다. 더 이상 일정을 늦출 수 없는 두 사람은 게임을 통해 회사 이름을 정하기로 했다. 다행히도 두 사람은 회사 이름의 길이에 대한 의견이 일치하고, 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길이 만큼 정해져있고 서로 최적의 방안을 고려하면 서로가 서로의 패를 알고 있어야 한다.

항상 맨 앞에 본인의 턴에 알파벳을 넣는게 디폴트다. (당연히 사람별로 koo는 가장 작은걸 맨앞, cube는 가장 큰걸 맨앞) 하지만 뒤에 넣어야 할 경우도 생기는데, 그래서 여러 경우의 수가 생긴다

1. 남은 ? 자리 중맨 앞에 넣는 경우 (koo: [A, B, C] , cube: [D, E, F])
   • koo는 자신의 가장 작은걸 넣는다 -> A??
   • cube는 자신의 가장 큰걸 넣는다 -> AF?
2. 남은 ? 자리 중 맨 뒤에 넣는 경우 (koo: [D, E, F] , cube: [A, B, C])
   • koo의 최소가 cube의 최대값보다 크면 koo본인껄 맨 앞에 넣는게 손해니까 일단 이후 상황을 고려해 최적의 방안인 본인의 최대값을 맨 뒤에 넣는다. -> ??F
   • cube의 최대가 koo의 최소값보다 작으면 cube본인껄 맨 앞에 넣는게 손해니까 일단 이후 상황을 고려해 최적의 방안인 본인의 최소값을 맨 뒤에 넣는다. -> ?AF

이렇게 고려해야할 여러 경우의 수를 나누어 진행해주면 된다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static String s1, s2;
    static Character[] koo, cube;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        //br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_16890_창업/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        s1 = br.readLine();
        s2 = br.readLine();

        koo = new Character[s1.length()];
        cube = new Character[s2.length()];

        for (int i = 0; i < s1.length(); i++) {
            koo[i] = s1.charAt(i);
        }

        for (int i = 0; i < s2.length(); i++) {
            cube[i] = s2.charAt(i);
        }

        int N = s1.length();

        Arrays.sort(koo);
        Arrays.sort(cube);

        Deque<Character> dq_half_koo = new ArrayDeque<>();
        for (int i = 0; i < (N + 1) / 2; i++) {
            dq_half_koo.offer(koo[i]);
        }

        Deque<Character> dq_half_cube = new ArrayDeque<>();
        for (int i = N - N / 2; i < N; i++) {
            dq_half_cube.offer(cube[i]);
        }

        char[] res = new char[N];
        Arrays.fill(res, '?');

        int left = 0, right = N - 1;

        for (int i = 0; i < N; i++) {
            //koosaga턴
            if (i % 2 == 0) {
                if (!dq_half_cube.isEmpty() && dq_half_cube.peekLast() <= dq_half_koo.peekFirst()) {
                    // [D, E, F]
                    res[right--] = dq_half_koo.pollLast(); // ??'F'
                } else {
                    // [A, B, C]
                    res[left++] = dq_half_koo.pollFirst(); // 'A'??
                }
            }
            //cubelover턴
            else {
                if (!dq_half_koo.isEmpty() && dq_half_cube.peekLast() <= dq_half_koo.peekFirst()) {
                    // [A, B, C]
                    res[right--] = dq_half_cube.pollFirst(); // ?'A'F
                } else {
                    // [D, E, F]
                    res[left++] = dq_half_cube.pollLast(); // A'F' ?
                }
            }
        }
        System.out.println(new String(res));
        bw.flush();
        bw.close();
        br.close();
    }
}