[Java]BOJ 1026 : 보물

https://www.acmicpc.net/problem/1026

🚩문제

🔓문제해결

1.배열A와 배열B의 똑같은 위치에 있는 값끼리 각각 곱하고 모두 더해준다.

=>이 값이 최소값이 되기 위해서는 최댓값*최솟값을 계속 해줘야한다.

2.문제에서 B는 재배열하면 안된다는 조건이 있다.

3.우선 A배열을 오름차순 해준다.

4.내림차순된 B배열의 값을 가져오기위해 인덱스를 사용한다.

5. 새로운 배열 C에 인덱스값을 넣어준다.

 

6.배열C의 정렬을 Comparator의 compare를 오버라이드하여 배열B를 기준으로 맞춰준다.

(배열B에 있는값을 내림차순한다 -> 그 값의 위치값을 배열C에 넣는다. )

 

7.for문을 돌면서 배열a와 배열b를 각각 곱하면서 결과값에 더해준다.

(배열B는 배열C에서 값을 가져와서 사용한다.)

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


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

        st=new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) { //a배열 입력받음
            arrA[i]=Integer.parseInt(st.nextToken());
        }

        st=new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) { //b배열 입력받음
            arrB[i]=Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arrA); //a 오름차순 정렬

        Integer [] bIndex = new Integer[arrB.length];
        for(int i=0; i<arrB.length; i++){
            bIndex[i]=i;
        }
        Arrays.sort(bIndex, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return arrB[o1] - arrB[o2]; 
            }
        }); //오름차순 정렬
        int result=0; //결과값 저장
        for(int i=0; i<n;i++){
            result+=arrA[n-1-i]*arrB[bIndex[i]];
        }
        System.out.println(result);
    }
}

메모리 : 14324KB, 시간 : 104ms