[백준] 2923번 숫자게임

문제 설명

• https://www.acmicpc.net/problem/2923
• Gold 1
• 풀이시간 : 25분

문제 풀이

• 그리디한 접근과 투 포인터를 이용하여 풀이하였다.
• 우선 문제에서 특정 두 집단의 합의 최대의 최소값을 구하려면 한 집단에서는 오름차순, 한 집단에서는 내림차순 정렬하여 선택하고 더한값의 최대값을 구해주면 된다.
• 단순히 위처럼 진행한다면 각 라운드별 O(N)으로 계산 가능하지만 시간초과가 발생한다. (N <= 10만)
• 숫자의 범위가 1~100인점을 감안하여 각 집합마다 크기가 101인 배열을 두고 숫자가 주어질때마다 해당 인덱스 값을 올려준다.
• 투 포인터를 이용하여 한 집단에서는 1->100으로 인덱스를 이동시키고 다른 집단에서는 100->1으로 인덱스를 이동시켜주며 합의 최대값을 구해주면 O(200)으로 계산이 가능하다.

소스 코드 (JAVA)

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

class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    static int N;
    static int[] arr1 = new int[101];
    static int[] arr2 = new int[101];

    static void solve() throws IOException {
        int[] tmp1 = arr1.clone();
        int[] tmp2 = arr2.clone();
        int ind1 = 1;
        int ind2 = 100;
        int max = 0;
        while(ind1 <= 100 && ind2 >= 1) {
            if (tmp1[ind1] == 0) {
                ind1++;
                continue;
            }

            if (tmp2[ind2] == 0) {
                ind2--;
                continue;
            }
            max = Math.max(max, ind1 + ind2);

            if (tmp1[ind1] > tmp2[ind2]) {
                tmp1[ind1] -= tmp2[ind2];
                ind2--;
            } else if (tmp1[ind1] < tmp2[ind2]) {
                tmp2[ind2] -= tmp1[ind1];
                ind1++;
            } else {
                ind1++;
                ind2--;
            }
        }
        bw.write(max + "\n");
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr1[Integer.parseInt(st.nextToken())]++;
            arr2[Integer.parseInt(st.nextToken())]++;
            solve();
        }
        bw.flush();
    }

    public static void main(String[] args) throws IOException {
        input();
    }
}

/**
 * 숫자 게임 (23:45)
 *
 * - 무조건 각각의 최대값과 최소값을 매칭시켜야함
 * - 크기가 101인 배열 2개를 놓고 하나는 왼쪽 하나는 오른쪽부터 포인터를 이동시키며 매칭시킨다. O(200)
 */