[프로그래머스] 최솟값 만들기

---

프로그래머스 Lv2 - 최솟값 만들기 문제

프로그래머스 코딩테스트 문제 중 레벨 2 K번째 수 문제를 풀이했다.

정렬이 필요한 문제이지만 어떻게 최적해를 구할까라는 관점에서 보았을 때는 그리디 알고리즘 방식으로 최적해를 구하였다
내가 생각해 최적해는 아래와 같다.

"A 배열의 가장 큰 수와 B 배열의 가장 작은 수를 곱하고, 그 다음 큰 수와 그 다음 작은 수를 곱해 나가다보면 결국에는 가장 최솟값이 나온다."

처음에는 코드의 가독성을 위해 A 배열은 오름차순 정렬, B 배열은 내림차순 정렬하여 아래와 같이 풀이해 보았지만 효율성 테스트에서 시간 초과를 받아서 불필요한 래핑과 내림차순 정렬을 사용하지 않고 다시 시도해보았더니 효율성 테스트까지 통과했다.
다른 사람의 풀이를 보니 우선순위 큐를 사용해 풀이한 케이스도 많이 보았고 더 빠르다고 하더라...

가독성을 위해 시도해 본 코드

import java.util.*;

class Solution
{
    public int solution(int []A, int []B)
    {
        int answer = 0;
        
        Integer[] ascA = Arrays.stream(A).boxed().toArray(Integer[]::new);
        Arrays.sort(ascA);
        
        Integer[] descB = Arrays.stream(B).boxed().toArray(Integer[]::new);
        Arrays.sort(descB, Collections.reverseOrder());
        
        int loopLen = A.length - 1;
        for(int i = 0; i <= loopLen; i++) {
            answer += ascA[i] * descB[i];   
        }

        return answer;
    }
}

MakeMinValue.java

package com.example.Programmers.Lv2;

import java.util.Arrays;

/**
 * 프로그래머스 Lv2 - 최솟값 만들기
 * 정렬 문제
 */
public class MakeMinValue {
    public int solution(int[] A, int[] B) {
        int answer = 0;

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

        int loopLen = A.length - 1;
        for (int i = 0; i <= loopLen; i++) {
            answer += A[i] * B[loopLen - i];
        }

        return answer;
    }
}

MakeMinValueTest.java

package com.example.Programmers.Lv2;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class MakeMinValueTest {
    @Test
    public void testMakeMinValue() {

        MakeMinValue mmv = new MakeMinValue();

        int result1 = mmv.solution(new int[] { 1, 4, 2 }, new int[] { 5, 4, 4 });
        int result2 = mmv.solution(new int[] { 1, 2 }, new int[] { 3, 4 });

        int expected1 = 29;
        int expected2 = 10;

        assertEquals(expected1, result1);
        assertEquals(expected2, result2);

    }
}