[Programmers] Lv2_최솟값 구하기 (JAVA)

💻JAVA 코드 바로보기

 

 

 

□문제 설명

길이가 같은 배열 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 이하의 자연수

---

□입출력 예

A	B	answer
[1, 4, 2]	[5, 4, 4]	29
[1,2]	[3,4]	10

 

 

□입출력 예 설명

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

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

 

---

🌼 JAVA 알고리즘

 

□초기화면

 

 

 

 

□풀이과정

A와 B의 요소의 곱의 누적값이 최소로 나오기 위해서는 서로의 최댓값과 최솟값을 곱해주어야 한다. 예를 들어서 A의 최솟값 1과 B의 최댓값 5를 곱하고, A의 최댓값 4와 B의 최솟값 4를 곱하여 (나머지 요소 포함) 최소결과 29가 나온다.

A	B	sorted_A	sorted_B	result
[1, 4, 2]	[5, 4, 4]	[1,2,4]	[5,4,4]	1*5+2*4+4*4=29

A	B	sorted_A	sorted_B	result
[1,2]	[3,4]	[1,2]	[4,3]	1*4+2*3=10

 

위와같은 방식으로 코드를 구현하면 A와 B배열을 각각 오름차순, 내림차순으로 정렬한 후 순차적으로 누적합시키면 된다. 이때 코드의 효율성을 위해 Selection 방식을 사용하였다.

 

[알고리즘] 선택 정렬(selection sort)이란 - Heee's Development Blog

 

class Solution
{
    public int solution(int []A, int []B)
    {
        int answer = 0;
        
        
        //selection sort_A
        for(int i=0;i<A.length;i++){
            int min = i;
            for(int j=i+1;j<A.length;j++){
                if(A[j]<A[min]) min = j;
            }
            int temp = A[min];
            A[min] = A[i];
            A[i] = temp;
        }
        
        //selection sort_B
        for(int i=0;i<B.length;i++){
            int max = i;
            for(int j=i+1;j<B.length;j++){
                if(B[j]>B[max]) max = j;
            }
            int temp = B[max];
            B[max] = B[i];
            B[i] = temp;
        }
        

        for(int i=0;i<A.length;i++){
            answer+=A[i]*B[i];
            //System.out.println(A[i]+B[i]);
        }
    

        return answer;
    }
}

Selection Sort정도의 시간복잡도라면 효율성을 통과할 수 있다고 생각했지만 ㅜ  아쉽게도 대부분 시간초과가 나타났다. 그 다음으로 가장 빠른 Quick Sort를 사용하였다.

 

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

 

 

 

 

 

 

 

□완성코드

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

        return answer;
    }
    public void QuickSort(int[] arr,int start, int end) {
        int part=partition(arr,start,end);
        if(start<part-1) QuickSort(arr,start,part-1);
        if(end>part) QuickSort(arr,part,end);
    }
    public int partition(int[] arr,int start,int end) {
        int pivot=arr[(start+end)/2];
        while(start<=end) {
            while(arr[start]<pivot) start++;
            while(arr[end]>pivot) end--;
            if(start<=end) {
                swap(arr,start,end);
                start++;
                end--;
            }
        }
        return start;
    }
    public void swap(int[] arr,int start,int end){
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }
}

 

 

 

 

 

 

 

 

 

---

□링크

About Me

 

코딩테스트 연습 - 최솟값 만들기