최솟값 만들기

Posted on Edited on In , ,

문제정의

두 배열에서 한 숫자씩 뽑아 둘의 곱을 더해나갈 때 최솟값을 구하는 문제이다. 단 중복으로 숫자를 뽑는 것은 허용하지 않는다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package level2;

import java.util.Arrays;

public class MakeMin {

    //프로그래머스 문제풀이 level2 최솟값 만들기

    public static void main(String[] args) {
        int[] A = {1, 4, 2};
        int[] B = {5, 4, 4};

        int answer = 0;
        Arrays.sort(A);
        Arrays.sort(B);
        for(int i = 0; i < A.length; i++)
            answer += A[i] * B[A.length-i-1];
        
        System.out.println(answer);
    }
    
}
최솟값을 만들기 위해선 각각의 배열에서 가장작은수와 가장큰수가 곱해져 나가야한다. 이를 생각해내면 코드는 단순하다. 두 배열을 정렬하고 하나는 앞에서부터 하나는 뒤에서부터 뽑아 곱해서 더하면 된다.

최종적인 시간복잡도는 배열의 길이를 n이라고 할 때, 정렬을 사용하였으므로 \(O(nlogn)\)이다.

테스트