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

 

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

프로그래머스

 

풀이과정

내 생각에는 일단 최솟값을 만들기 위해서는 극단적 예시로 배열이

A : [ 1, 2, 3 ]

B : [ 1, 2, 3 ]

이렇게 주어졌을때 오름차순 * 오름차순보다는  (결과 1*1 + 2*2 + 3*3 = 14)

A : [ 1, 2, 3 ]

B : [ 3, 2, 1 ]

이렇게 오름차순*내림차순을 곱했을때 최솟값일거라는 생각이었고, (결과 1*3 + 2*2 + 3*1 = 10)

그 생각이 맞았다.

 

1. 코드

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

 

이렇게 작성했고, 테케는 다 맞았다.

 

근데 이 자식이 효율성에서 밀리네?

아마  B를 내림차순하는 과정에서 B를 Integer 배열로 변환할때 효율성이 떨어지나보다. (  O( nlogn)  )

그래서 A를 내림차순하고 B를 오름차순 했더니 테스트1,4번이 시간초과 뜸ㅋㅋ

 

 

2. 수정코드

import java.util.*;
class Solution
{
    public int solution(int []A, int []B)
    {
        int answer = 0;
        Arrays.sort(A);
        Arrays.sort(B);
        
        int n = B.length;
        for (int i = 0; i < n / 2; i++) {
            int temp = B[i];
            B[i] = B[n - 1 - i];
            B[n - 1 - i] = temp;
        }
        
        for(int i = 0 ;  i < A.length; i++){
            answer+=A[i]*B[i];
        }
        return answer;
    }
}

 

그래서 그냥 B를 오름차순 한 후에 내가 친절히 앞뒤를 바꿔서 내림차순으로 만들어줬다.

그리고 성공은 했다.

 

 

회고

lv2로 넘어오니까 시간복잡도를 이제는 슬슬 챙겨야할때가 왔구만,,