[BOJ 길라잡이/Java] 5일차 #1026 보물

알고리즘 분류

- 수학

- 그리디 알고리즘

- 정렬

 

B에 있는 수는 재배열하면 안 된다고 되어 있긴 한데..

S의 최솟값을 만들려면 A는 오름차순, B는 내림차순 정렬해서 index 1부터 곱 돌리면 되겠다..

라는 생각이 들어서 그렇게 풀었는데 통과는 됐다.

(구글링 해보니까 다 이렇게 했던데 ??)

 

일단 내가 작성한 코드는 다음과 같다.

 

두 배열 오름차순, 내림차순 정렬

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        ArrayList<Integer> A = new ArrayList<>();
        ArrayList<Integer> B = new ArrayList<>();
        int sum = 0;
        
        for (int i = 0; i < N; i++) {
            A.add(Integer.parseInt(st.nextToken()));
        }

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

        for (int i = 0; i < N; i++) {
            B.add(Integer.parseInt(st.nextToken()));
        }

        Collections.sort(A);
        Collections.sort(B, Comparator.reverseOrder());

        for (int i = 0; i < N; i++) {
            sum += A.get(i) * B.get(i);
        }

        System.out.println(sum);
    }
}

 

ArrayList 말고 배열 만들어서 해도 비슷하게

Arrays.sort() 사용하면 된다!

다만, Arrays.sort()는 래퍼클래스만 가능하므로 배열B는 int[]이 아닌 Integer[]로 생성해야 한다!

이후 Arrays.sort(B, Collections.reverseOrder()); 해주기