[백준 | 1026] 보물 - Java

📃 제출

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[] a = new int[N];
        int[] b = new int[N];
        String[] s;

        s = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            a[i] = Integer.parseInt(s[i]);
        }

        s = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            b[i] = Integer.parseInt(s[i]);
        }

        Arrays.sort(a);
        Arrays.sort(b);

        int result = 0;
        for (int i = 0; i < N; i++) {
            result += a[N - 1 - i] * b[i];
        }

        bw.write(result + "");
        br.close();
        bw.flush();
        bw.close();
    }
}

✏ 풀이

A 배열의 가장 큰 값을 B 배열의 가장 작은 값과 곱하고, 그 다음으로 큰 값을 그 다음 작은 값과 곱해 나가는 방식으로 문제를 해결할 수 있을 것이라 생각했습니다. 이를 위해, A 배열을 오름차순으로 정렬하고, B 배열을 내림차순으로 정렬하여 문제를 해결할 수 있습니다. 그러나 여기서는 두 배열 모두 오름차순으로 정렬한 후, A 배열을 역순으로 순회하고 B 배열은 정순으로 순회하여 연산을 수행했습니다.

과정 )

1. 초기 배열

• A = {1, 1, 1, 6, 0}
• B = {2, 7, 8, 3, 1}

2. 오름차순 정렬

• A = {0, 1, 1, 1, 6}
• B = {1, 2, 3, 7, 8}

3. 최솟값 계산

• A 배열은 역순, B 배열은 정순
• 6 * 1 = 6
• 1 * 2 = 2
• 1 * 3 = 3
• 1 * 7 = 7
• 0 * 8 = 0

3. 반환

• 6+2+3+7 = 18

시간 복잡도 분석

$$T(n) = O(n) + O(n) + O(n log n) + O(n log n) + O(n) = O(n log n) $$

•