백준 2923번 - 숫자 게임

문제

백준 2923번 - 숫자 게임

아이디어

가장 큰 값이 가능한 작게 하기 위해서는 한쪽은 가장 크고, 한쪽은 가장 작은 수여야 할 것이다. 이때 가능한 쌍을 모두 확인해보는데, 같은 숫자 쌍을 어떻게 효율적으로 중복 계산 하지 않는 것이 포인트다.

코드 구현 - 자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_2923 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        int[] A = new int[101];
        int[] B = new int[101];

        // 1
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            A[Integer.parseInt(st.nextToken())]++;
            B[Integer.parseInt(st.nextToken())]++;

            sb.append(getMax(A, B, i + 1)).append("\n");
        }

        System.out.print(sb);
    }

    /**
     * 2
     * @param A 현우가 말한 A
     * @param B 현우가 말한 B
     * @param total 현재까지 나온 수의 개수
     * @return 가능한 쌍의 합 중 가장 큰 값
     */
    private static int getMax(int[] A, int[] B, int total) {
        //복사
        int[] x = Arrays.copyOf(A, A.length);
        int[] y = Arrays.copyOf(B, B.length);

        int xIdx = 1;
        int yIdx = 100;
        int max = 0;    //가장 큰 값
        int used = 0;   //총 사용된 수의 개수

        while (used < total) {
            while (xIdx <= 100 && x[xIdx] == 0) xIdx++; //작은 수에서 큰 수로
            while (yIdx >= 1 && y[yIdx] == 0) yIdx--;   //큰 수에서 작은 수로

            //둘 중 적게 나온 수만큼 쌍을 만들 수 있음
            int use = Math.min(x[xIdx], y[yIdx]);
            //가장 큰 쌍의 합 갱신
            max = Math.max(max, xIdx + yIdx);

            //쌍의 개수만큼 차감 및 사용된 수의 개수 누적
            x[xIdx] -= use;
            y[yIdx] -= use;
            used += use;
        }

        return max;
    }
}

1

• 현우가 말한 숫자 A와 B에 대해 각각 빈도수를 누적한다.

2

• 기존 빈도수 배열에 영향이 없게 복사해서 사용한다.
• 현재까지 나온 숫자들 중에서 가능한 쌍의 합을 모두 찾아본다. 이때 한쪽은 1부터, 한쪽은 100부터 시작해서 최대한 가장 큰 값을 가능한 작게 만들 수 있도록 한다.
• 그리고 사용된 수의 개수를 누적할 때가 포인트로, 배열에는 빈도수가 누적되어 저장되어 있다. 이 빈도수만큼은 똑같은 쌍이기 때문에 중복 계산을 방지하는 역할을 해준다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N * 100)