[Lv.2] 최솟값 만들기 [프로그래머스_코딩테스트] [정렬, 그리디] [25분]

🔍 문제 요약

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

프로그래머스

숫자의 배열 A와 B가 주어지고 A와 B에서 숫자 하나씩을 뽑아가면서 숫자의 곱을 한 값들의 합이 최소가 되는 경우 결과를 반환하는 문제.

🧠 나의 접근 방식과 시행착오

5분 걸린 문제. 맨처음 문제를 읽으면서 A,B의 길이가 같기 때문에 이중 반복을 돌리지 않을것이라는 추측과, Dictionary를 써서 이미 고른 것을 다시 체크하지 않게 해야 하려나?란 생각을 하면서 읽었다. 문제를 다 읽고 나서는 최소가 되는 곱의 합을 구하는 것이니깐 확신까진 없었지만 한 쪽은 오름차순, 한쪽은 내림차순을 하고 순서대로 곱하기를 해서 더하면 되지 않을까란 생각을 했음. 그리고 그렇게 해서 테스트 케이스는 모두 통과해서 넘어가게 되었다.

public int solution(int[] A, int[] B)
{
    // 각 숫자의 곱의 합의 최솟값을 구하기 위해서는 한 쪽을 오름 차순, 한쪽은 내림차순하고 곱을 한 합
    Array.Sort(A);
    Array.Sort(B);
    Array.Reverse(B);

    int sum = 0;

    for (int i = 0; i < A.Length; i++)
    {
        sum += A[i] * B[i];
    }

    return sum;
}

✅ 풀이 코드

한 가지 다른 풀이 방법으로 Linq의 방법도 알려주었으나 역시 성능면에서 불안하다는 생각이 들기에 그냥 이런 방법도 있다는 정도만 알면 될 듯 하다.

return A.OrderBy(x => x)
        .Zip(B.OrderByDescending(x => x), (a, b) => a * b)
        .Sum();

🔄 정리

코딩 테스트를 풀 때는 일단 먼저 해답을 내는 법칙을 빠르게 찾을 수 있어야 한다는 생각이 든다. 위 문제처럼 작은 수 * 큰 수끼리의 조합으로 해야 합이 최소가 나온다는 것이 핵심인데 이게 맞나란 생각이 들 때가 많기에 기억해두면 좋을 듯 하다.