정렬_1026_보물

연초에 계획했던 바와는 다르게 또 다시 귀찮음이 용솟음 치며 열심히 알고리즘을 풀고 정리하겠다 했던 다짐이 한 동안 죽어있다가 연말이 되어서야 다시 살아난다. 

나름 직장인이 된지도 어언 만 2년차를 바라보고 있는 시점에 진짜로 다시금 마음을 잡고 꾸준히 공부를 하고자 한다. 
매일 공부를 할 수 있는 주기적인 시간이 나오는 것은 아니지만, 시간이 되는 날에라도 놀지 않고 한 문제씩이라도 문제를 풀면서 개념을 정리하고자 한다. 

오늘 풀어볼 문제는 백준 1026에 속해 있는 정렬 파트 문제이다. 

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

1026번: 보물

 

문제 분석

• 길이가 같은 두 개의 정수 배열 A, B가 주어진다. 
• B의 원소는 순서를 변경하면 안되며 A의 원소만 문제의 목적에 부합하도록 순서를 정렬할 수 있다. 
• 가장 큰 상금을 얻는 방법은 두 배열의 원소의 곱의 합이 최소가 되는 값을 찾아야 한다. 
• 배열의 최대 크기는 50이며, 시간 제한 은 2초 약 2억 번의 연산이 가능하기 때문에 중첩 for문을 사용해도 시간 초과의 우려는 적다. 
• 또한 원소는 100이하의 음이 아닌 정수이기 때문에 음수가 더해져서 총 합이 작아질 우려 또한 없다. 
• 쉽게 생각하여 곱의 합의 최소를 구하기 위해서는 최솟값과 최댓값을 곱한 합을 구해야 한다는 것이다. 
• B의 원소는 순서가 고정이기 때문에 그 순서에 맞게 A의 원소를 정렬하여 각 인덱스에 해당하는 곱의 합을 구한다. 

문제 접근 

• 이 문제를 물리적인 관점으로 바라보면 A의 최솟값이 B의 최댓값의 인덱스와 동일하게 배치되도록 정렬해야 한다. 
• 하지만 정렬보다 중요한 것은 곱의 합이 최소만 되면 된다는 것. 논리적인 구조를 보면 B의 원소 또한 정렬해도 된다는 것이다. 
• 물리적인 구조로 맞추다 보면 구조를 짜맞추는 것도 어려울 뿐더러, 그 구조를 맞춰서 구한 곱의 합이 논리적인 구조로 구성한 배열의 곱의 합과 같은 결과가 나올 것이다. 
• 즉 A는 오름차순, B는 내림차순으로 정렬한 후에 곱의 합을 구하면 된다. 말이 좀 어려우니 간단히 그림으로 예시를 보자.

 

문제에 나와있는 예시1을 보자. 주어진 배열의 형태는 아래와 같다.

 

위의 배열을 물리적인 구조로 A의 최소 * B의 최대를 계산하기 위해 A만 정렬하면 아래의 결과가 나온다.

S = 1 * 2 + 1 * 7 + 0 * 8 + 1 * 3 + 6 * 1 = 18이 된다. 
하지만 위에서 말했듯이 문제에서 제시한 조건을 그대로 B를 정렬하지 않고 B의 구성에 맞게 A를 사용자 정렬하는 것은 효율성이 좋지 않다. 하여 아래와 같이 같은 결과를 도출할 수 있도록 논리적인 구조로 정렬한다. 

핵심은 A의 최소 * B의 최대를 기준으로 두 배열을 정렬한다.

 

 

A를 오름차순, B를 내림차순으로 하던 A을 내림차순, B를 오름차순으로 하던 결과는 같다. 위에서 말한 핵심을 기준으로 두 배열일 반대의 기준으로 정렬되면 된다는 점이다. 아래의 전체 소스를 첨부하는 것으로 글을 마치겠다. 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws  Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> A = new ArrayList<>();
        ArrayList<Integer> B = new ArrayList<>();

        //list A 초기화
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<N; i++){
            A.add(Integer.parseInt(st.nextToken()));
        }

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

        //A는 오름차순, B는 내림차순
        Collections.sort(A);
        Collections.sort(B, Collections.reverseOrder());

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

        System.out.println(S);
    }
}