[프로그래머스,Level 2] 최솟값 만들기 (JAVA 구현)

 

- 첫 풀이 및 정답풀이

  이 문제에서 우선 잘못 출력된듯한 부분이 있는데, 문제 설명 부분의 예시에서 "A에서 첫번째 숫자인 1, B에서 두 번째 숫자인 5를 뽑아 곱하여 더합니다." 라고 나와있지만, 입출력 예를 보면 알 수 있듯이 B에서 5의 위치는 첫 번째이기 때문에 이를 혼동하면 안 된다.

 

  처음 문제를 읽고 이해한 것은 예를 들어 A에서 0번째 인덱스를 선택했다면, B에서 0번째 인덱스를 선택하면 안 된다고 이해했지만, 예시를 설명하는 부분을 보면 A와 B 배열 모두 첫 번째 숫자를 선택했기 때문에 잘못 이해했다는 것을 깨달았다. 다시 잘 생각해보니, 한 번 선택한 숫자는 다시 사용할 수 없다는 소리였다. 

 

---

  문제에 대한 이해를 마치고, 어떻게 풀어볼까 고민하던 중 DFS를 활용해 완전 탐색을 수행하는 방법을 떠올렸다. 그러나 이 방법은 코딩 자체에 생각이 많이 필요하고 시간도 많이 소요되므로 더 간단한 방법이 없을까 생각해보던 중 간단한 생각이 떠올랐다.

 

  문제 자체가 요구하는 바는 두 개의 배열에 있는 값들을 이용해 최솟값만을 찾으면 되므로, A배열에서의 최솟값 * B배열에서의 최댓값을 수행하면 최솟값을 만들 수 있을 것 같다고 생각했다. 따라서 A는 오름차순 정렬, B는 내림차순 정렬을 수행한 뒤, 배열의 길이만큼 더해 최솟값을 만들 수 있었다. 

 

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

class Solution
{    
    public int solution(int []A, int []B)
    {
        int answer = 0;
        // 1. B 배열은 내림차순 정렬.
        Integer[] b = new Integer[B.length];
        
        // 2. Collections.sort()를 위해 Wrapper클래스 배열에 저장.
        for(int i = 0 ; i<b.length;i++)
            b[i] = B[i];
        
        // 3. A 배열은 오름차순 정렬.
        Arrays.sort(A);
        // 4. b 배열은 내림차순 정렬.
        Arrays.sort(b,Collections.reverseOrder());
        
        // 5. 최솟값을 만들기 위해 배열의 길이만큼 각 배열의 값을 곱한 뒤, 더해준다.
        for(int i = 0;i<A.length;i++){
            answer+=(A[i] * b[i]);
        }        

        return answer;
    }
}