[Level2] 최솟값 만들기 답안 및 풀이

◇ 문제 설명

길이가 같은 배열 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 합니다.

 

 

◇ 초기 내용

※ [출처] 프로그래머스-코딩테스트 연습-문제명

※ 초기 내용을 참고하여 문제에 맞는 코드를 작성하세요.

class Solution
{
    public int solution(int []A, int []B)
    {
        int answer = 0;

        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("Hello Java");

        return answer;
    }
}

 

---

◇ 풀이 과정

[최솟값 구하기] 문제의 핵심은 길이가 같은 두 배열 A, B가 있을때 각각 한 개의 숫자를 뽑아 두수를 곱한 후, 두수를 곱한 값을 누적하여 더했을때 최종적으로 누적된 값이 최소가 되도록 만드는 것이다.

 

처음 이 문제를 보았을때에는 누적된 모든 경우의 수를 따져 최소인 수를 구해야하나 하는 생각이 들었지만 문제를 풀다보니 규칙이 보였다.

 

그 답은 각 배열에서 뽑는 한개의 숫자에 있었다.

각 배열에서 뽑는 한개의 숫자에 대하여 서로 평균을 맞춰주는것이다.

예를 들어, A = [1, 4, 2] , B = [5, 4, 4] 라면

A에서 가장 작은 수인 1, B에서 가장 큰 수인 5를 곱하여, 1 x 5 = 5

A에서 두번째로 작은 수인 2, B에서 두번째로 큰 수인 4를 곱하여, 2 x 4 = 8

A에서 가장 큰수인 4, B에서 가장 작은 수인 4를 곱하여, 4 x 4 = 16

즉, 5 + 8 + 16 = 29로 위 예시와 같은 답이 나오게 된다.

 

이를 표로 설명하자면,

A(오름차순정렬)	1	4	2
B(내림차순정렬)	5	4	4
answer	1 x 5	4 x 4	2 x 4

와 같은 풀이를 이용하여 문제를 풀고자 하였다.

 

◇  참고 사항

<정렬>

이번 문제는 '효율성'을 중점적으로 보는 문제였다. 이 효율성을 가르는 코드가 바로 '정렬'알고리즘이었는데 바로 이 정렬 알고리즘을 어떻게 작성하느냐에 따라 효율성 테스트의 통과여부가 갈라진다.

 

우선 오름차순을 기준으로 크게 2가지의 정렬 코드를 소개하겠다.

 

첫번째로는 선택 정렬이다. 

• 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다.
  https://terms.naver.com/entry.naver?docId=2270435&cid=51173&categoryId=51173

선택 정렬

• 선택정렬은 가장 이해하기 쉽고, 직관적인 정렬 방법이지만 효율이 크게 떨어진다는 단점이 있다.
  선택정렬의 시간복잡도는 O(n제곱)으로 매우 속도가 느린편이다.
• 아래는 선택정렬의 코드이다.
  

  for (int i = 0; i < n-1; i++) {
  	min = arr[i];
      index = i;
  	for (int j = i+1; j < n; j++) {
  		if (min > arr[j]) {
  			min = a[j];
              index = j;
  		}			
  	}
      a[index] = a[i];
      a[i] = min;
  }​

   
•  선택정렬의 정렬과정
  <초기 배열>
  

  5

  2

  1

  4

  3

  <1단계>
  

  1

  2

  5

  4

  3

  <2단계>
  

  1

  2

  5

  4

  3

  <3단계>
  

  1

  2

  3

  4

  5

  <4단계>
  

  1

  2

  3

  4

  5

  <5단계>
  

  1

  2

  3

  4

  5

두번째로는 퀵정렬이다. 

• 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법이다.
  https://terms.naver.com/entry.naver?docId=2270444&cid=51173&categoryId=51173

퀵 정렬

• 퀵정렬은 정렬 중 꽤 높은 효율을 자랑하며, 시간복잡도로 O(logn * n)
• 아래는 퀵정렬의 코드이다.
  

  int i, j, pivot, temp;
  if(left<right){
  	pivot = arr[left];
  	i = left;
  	j = right;
  	while(i<j){
  		while(i<right&&arr[i]<=pivot) i++;
  		while(j>left&&arr[j]>=pivot) j--;
  	}
                 
  	if(i<j){
  		temp = arr[i];
  		arr[i] = arr[j];
  		arr[j] = temp;
  	}
  }
  arr[left] = arr[j];
  arr[j] = pivot;
  
  QuickSort(arr, left, j-1);
  QuickSort(arr, j+1, right);​

 

◇ 답안

class Solution
{
    public int solution(int []A, int []B)
    {
        int answer = 0;
        
        //배열의 크기를 저장하는 변수 생성
        int length = A.length;
        
        //첫번째 배열은 오름차순 정렬
        A = QuickSort(A, 0, length-1, true);
        
        //두번째 배열은 내림차순 정렬
        B = QuickSort(B, 0, length-1, false);
        
        //첫번째 오름차순 정렬 확인 코드
        //SortCheck(A, length);
        
        //두번째 내림차순 정렬 확인 코드
        //SortCheck(B, length);
        
        //각 요소를 곱한 후, answer에 누적하여 저장
        for(int i = 0; i<length; i++){
            answer += A[i]*B[i];
        }
        
        return answer;
    }
    
    //퀵정렬을 이용하여 오름/내림차순 정렬
    //ch가 true이면 오름차순, ch가 false이면 내림차순을 나타냄
    int[] QuickSort(int arr[], int left, int right, boolean ch){
        int i, j, pivot, temp;
        if(left<right){
            pivot = arr[left];
            i = left;
            j = right;
            while(i<j){
                if(ch==true){
                    while(i<right&&arr[i]<=pivot) i++;
                    while(j>left&&arr[j]>=pivot) j--;
                }else{
                    while(i<right&&arr[i]>=pivot) i++;
                while(j>left&&arr[j]<=pivot) j--;
                }
                
                if(i<j){
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
            arr[left] = arr[j];
            arr[j] = pivot;
            
            QuickSort(arr, left, j-1, ch);
            QuickSort(arr, j+1, right, ch);
        }
        return arr;
    }
    
    // 정렬 확인을 위한 출력 코드
    // 프로그래머스 내, 출력 코드를 포함하여 제출 시, 효율성 테스트에서 막힐 수 있음(주석처리)
    // void SortCheck(int arr[], int length){
    //     for(int i = 0; i<length; i++){
    //         System.out.print(arr[i] + " ");
    //     }
    //     System.out.println();
    // }
}

 

◇ 실행결과

최솟값 구하기 실행결과

 

◇ 효율성 테스트 결과

최솟값 구하기 효율성 테스트 실행결과

 

◇ 출처

https://programmers.co.kr/learn/challenges

코딩테스트 연습