[Java] 프로그래머스(level-2) - 최솟값 만들기

입출력 예시

Input-1
A = [1, 4, 2]
B = [5, 4, 4]
Output-1
29

Input-2
A = [1, 2]
B = [3, 4]
Output-2
10

문제 풀이

A와 B 배열에서 두 수 를 뽑아 곱한 값을 누적하여 더할 때, 최소로 되도록 해야한다.
그렇다면 두 수의 차가 클 수록 곱한 값은 작아지기에 최소로 만들 수 있다.
어떻게 두 수의 차가 큰 수를 뽑을 수 있을까?

A배열은 오름차순으로, B배열은 내림차순으로 정렬하여 순서대로 뽑는다면 A배열에서 가장 작은수와 B배열에서 가장 큰 수를 뽑을 수 있다.

한 번 코드로 작성해보자.

A배열 오름차순 정렬

먼저, A배열을 오름차순으로 정렬하자.

Arrays.sort(A);

B배열 내림차순 정렬

그리고 B배열을 내림차순으로 정렬하자.

Integer[] reverse_B = Arrays.stream(B).boxed().toArray(Integer[]::new); 
Arrays.sort(reverse_B, Collections.reverseOrder());

스트림 활용 내림차순 정렬 방식 - Arrays.stream(B).boxed().toArray(Integer[]::new)

1. 기본형 배열을 스트림 형태로 변경 : Arrays.stream(B)
2. int -> Integer (객체 형태로 변환) : boxed() -> 내부 코드는 아래와 같은 식이다.

    public final Stream<Integer> boxed() {
        return mapToObj(Integer::valueOf, 0);
    }
   

3. 객체 스트림 형태를 배열의 형태로 변경 Stream.toArray(Type[]::new) => toArray(Integer[]::new);

효울성 테스트 시간초과

테스트케이스는 모두 통과했지만, 효율성 테스트에서 시간초과가 발생하였다.
스트림으로 내림차순 정렬 할 때 시간이 소요되는 것으로 생각하고 고쳐보기로 했다.

정렬 방식 변경

A와 B배열 모두 오름차순 정렬 후 A배열은 오름차순 인덱스로 접근하고, B배열은 내림차순 인덱스로 접근하였다.

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

작성한 코드를 제출하니 정상적으로 효율성 테스트를 통과하였다.

작성 코드

import java.util.*;

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

        long start = System.currentTimeMillis();
        solution2(A,B);
        long end = System.currentTimeMillis();
        System.out.println("\n수행시간 = " + (end-start));
    }

    public static int solution2(int[] A, int[] B) {
        int answer = 0;
        Arrays.sort(A);
        Arrays.sort(B);
        for(int i=0; i<A.length; i++) {
            answer += A[i] * B[B.length-i-1];
        }
        return answer;
    }
}

회고

• 배열을 정렬할 때 스트림을 활용한 내림차순 정렬 등, 특정 메서드를 활용하는 것도 좋지만, 마냥 효율적인 코드는 아닐 수도 있음을 느꼈다.