이 문제는 두가지로 풀이하였다.
첫번째는 완전 탐색을 하였고, 두번째는 탐욕적인 알고리즘으로 풀이하였다.
결론은 완전 탐색은 시간 초과가 나와서 두번째 방식으로 풀이했다.
각각의 풀이 방법을 정리해보겠다.

설명

1. 모든 경우의 수를 찾는 완전 탐색을 진행한다.

• output 배열의 자리수를 채운다.
  • 방문한 인덱스는 true로 표시한다.
• 배열이 가득차면 재배열된 A배열과 B배열을 각각 곱하여 결과를 뽑는다.
• 위를 반복하여 가장 큰 숫자를 찾는다.
  => 이 경우에 위를 순열을 구하는 것만 N!이다.(경우의 수를 잘 생각해보자!)
  => 이것은 시간복잡도가 아주아주 크기 때문에 시간 초과가 발생한다.

2. 탐욕적인 알고리즘으로 풀이한다.

• A와 B배열을 정렬한다.
• 정렬된 A와 B배열에서 A배열은 앞에서부터 B배열은 뒤에서부터 곱해나간다.

이 풀이에서 생각해볼 것이 두가지 있다.
1. Java 내부의 정렬은 어떤 알고리즘을 사용할까?

• Arrays.sort()
  • 듀얼피봇 퀵정렬(Dual Pivot QuickSort)를 사용한다.
  • 피봇을 2개를 두고 3개의 구간을 만들어 정렬한다. 랜덤 데이터에 대해서 평균적으로 퀵소트보다 좋은 성능을 낸다.
• Collections.sort()
  • Tim 정렬을 사용한다.
  • Tim 정렬은 삽입(Insertion) 정렬과 합병(Merge) 정렬을 결합하여 만들었다.

2. A배열은 앞에서부터 B배열은 뒤에서부터 곱해나가는 것이 왜 성립되는 것일까?
   • 이 부분은 재배열 부등식을 통해 증명할 수 있다. 이 글에서 증명은 생략한다.

코드

1. 모든 경우의 수를 찾는 완전 탐색을 진행한다. ->시간초과 발셍

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

public class Main {
	public static int MINIMUM_RESULT = Integer.MAX_VALUE;
    static int N;
    static int[] A;
    static int[] B;
    
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.iin));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        
        A = new int[N];
        B = new int[N];
        
        int[] output = new int[N];
        boolean[] visited = new boolean[N];
        
        // A 초기화
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
        	A[i] = Integer.parseInt(st.nextToken());
		}
        
        // B 초기화
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
        	B[i] = Integer.parseInt(st.nextToken());
		}
        perm(A, B, output, visited, 0, N);
        System.out.println(MINIMUM_RESULT);
	}
    
    static void perm(int[] a, int[] b, int[] output, boolean[] visited, int depth, int n) {
    	if (depth == n) {
        	int result = 0;
            for (int i = 0; i < n; i++) {
            	result += output[i] * b[i];
			}
            
            if (result < MINIMUM_RESULT) {
            	MINIMUM_RESULT = result;
			}
		}
        
        for (int i = 0; i < n; i++) {
        	if (visited[i] != true) {
            	visited[i] = true;
                output[depth] = a[i];
                perm(a, b, output, visited, depth + 1, n);
                visited[i] = false;
			}
		}
	}
}    

2. 탐욕적인 알고리즘으로 풀이한다.

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

public class Main {
    static int N;
    static int[] A;
    static int[] B;

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());   // 길이

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

        // A 초기화 -> A의 수를 재배열할 수 있고 B는 재배열할 수 없음
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        // B 초기화
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(A);
        Arrays.sort(B);

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

        System.out.println(result);
    }
}

Reference

• https://sabarada.tistory.com/m/138