최솟값 만들기 (programers > lev2 > Max_Min)

문제 링크

문제설명

길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면

• A에서 첫번째 숫자인 1, B에서 두번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
• A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
• A에서 세번째 숫자인 2, B에서 첫번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)

즉, 이 경우가 최소가 되므로 29를 return 합니다.

배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 A, B의 크기 : 1,000 이하의 자연수
• 배열 A, B의 원소의 크기 : 1,000 이하의 자연수

입출력 예

입출력 예 설명

입출력 예 #1 문제의 예시와 같습니다.

입출력 예 #2 A에서 첫번째 숫자인 1, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 4) 다음, A에서 두번째 숫자인 2, B에서 첫번째 숫자인 3을 뽑아 곱하여 더합니다. (누적된 값 : 4 + 6 = 10) 이 경우가 최소이므로 10을 return 합니다.

풀이

import java.util.*;
import java.util.stream.Collectors;

public class prog_2_최솟값만들기 {

    static public int solution(int []A, int []B)
    {
        int answer = 0;
        
        Arrays.sort(A); // 작은 -> 큰 순으로 정렬
        Arrays.sort(B);

        for(int i=0;i<A.length;i++) {
        	answer = answer + (A[i] * B[B.length-i-1]);
        }
        
        return answer;
    }
    
    public static void main(String[] args) {
		int a[] = {1,4,2};
		int b[] = {5,2,8,0};
		solution(a,b);
    	
	}
	
}

후기

처음에는 메모이제이션을 사용하거나, 식을 세워서 푸는 문제라고 생각했다.

하지만 수학적으로 생각해보면 간단한 문제였다.

1. 각 한번씩만 사용되면서
2. 누적된 값이 최소가 되게 하려면
3. A 배열의 제일 작은 값과 B 배열의 제일 큰값을 곱해주면 된다.

tip

1. 처음에는 B를 list로 변환해 내림차순으로 정렬하고 배열로 바꿔주려고 했다.(쓸데없이…)
2. Arrays.asList()의 사용은 non primitive (ex, String)만 가능하고 primitive는 불가능하다.
3. 굳이 primitive (ex, int)형의 배열을 list로 바꾸고 싶은경우에는 아래 처럼 사용한다. (이때, import java.util.stream.Collectors;)
4. List의 reverse 함수는 내림차순 정렬이 아닌 list의 원소들의 순서만 거꾸로 바꿀 뿐이다. (정렬 X)
5. 보통의 sort 함수는 오름차순이고, list를 내림차순으로 사용하고싶다면 아래의 함수를 사용한다.
6. list를 배열로 바꾸는 법도 까먹지 않도록 한다!

     2. Arrays.asList()
         
     3. List<Integer> list = Arrays.stream(B).boxed().collect(Collectors.toList());             -> 필수! import java.util.stream.Collectors;

     4. Collections.reverse(list);

     5. LinkedList<Integer> list = new LinkedList<Integer>();
        Collections.sort(list,Collections.reverseOrder());
 
     6. list.stream().mapToInt(k->k).toArray();
       

comparator 와 comparable의 차이점 설명하는 블로그