Lv.2 : 최솟값 만들기

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 길이가 같은 정수형 배열 A와 B가 입력된다.
• A와 B의 원소를 각각 하나씩 곱한 후 누적한 값의 최소값을 출력한다.

🔸 문제 풀이 🔸

• 원소곱의 누적합이 최소가 되려면, 가장 큰 수를 가장 작은 수와 곱해야 한다.
  
  • 그리디적인 관점이라고 할 수 있다.
• A와 B배열을 오름차순 정렬한다.
• 아직 사용하지 않은 원소중에서 가장 큰 수와 반대편의 배열의 가장 작은수를 곱해 누적하는 방식으로 계산한다.

---

🔸 코드 🔸

import java.util.Arrays;

class Solution
{
    public int solution(int []A, int []B)
    {
        int answer = 0;
        
        Arrays.sort(A);
        Arrays.sort(B);
        
        int aa = 0;
        int ab = A.length - 1;
        int ba = 0;
        int bb = ab;

        while(aa <= ab) {
            if(A[ab] > B[bb]) {
                answer += A[ab--]*B[ba++];
            } else {
                answer += A[aa++]*B[bb--];
            }
        }

        return answer;
    }
}

🔸 코드 해석 🔸

• 정수형 배열 A와 B를 오름차순 정렬한다.
• 각 배열의 최소값 인덱스와 최대값 인덱스를 나타낼 포인터 변수를 초기화한다.
• 포인터 변수가 교차 할 때까지 계산을 반복한다.
  • A배열의 최대값과 B배열의 최대값 중 큰 값과 그 반대 배열의 최소값을 곱해 누적한다.
  • 계산에 사용 된 원소를 빼기 위해서 인덱스를 이동시킨다.
• answer를 반환한다.

---

🔸 end 🔸

• 그리디적인 관점으로 문제를 풀이했는데, 생각보다 효율 좋게 잘 풀이한 것 같다.
• 잘 풀어낸 다른 사람들의 풀이도 비슷 한 것 같다.