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

문제 Link

https://school.programmers.co.kr/learn/courses/30/lessons/12941

프로그래머스

 

문제풀이 Key Point

• 가장 작은 값과 가장 큰 값을 곱한 결과들을 더해나가야 최소합을 구할 수 있다.
• 효율성을 고려하기 위한 고민이 필요하다.
  (아래에 설명되어 있음)

 

정확성은 통과 했으나 효율성에서 시간초과 발생

아래 코드가 효율성에서 시간초과가 난 이유

• 가장 작은 값과 가장 큰 값을 곱해 나가기 위해 A배열은 오름차순, B배열은 내림차순으로 정렬해 나가려고 했다.
• Collections.reverseOrder() 를 사용하기 위해 stream을 이용해서 B배열을 int 타입(primitive type)에서
  Integer 타입(reference type)으로 변환한 뒤에 Arrays.sort(배열, Collections.reverseOrder());를 수행해주었다.
• 내림차순 연산을 위해 stream이 들어가면서 더 많은 시간이 소요되게 되었다.
• 둘 다 오름차순 정렬 후, 'index'와 '배열길이 - index - 1'을 하게되면 최소값과 최대값을 가리키게 된다.

import java.util.Arrays;
import java.util.Collections;

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

        return answer;
    }
}

 

Java 문제풀이

import java.util.Arrays;
import java.util.Collections;

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

        return answer;
    }
}