프로그래머스 문제 : 최솟값 만들기

[프로그래머스] 최솟값 만들기 - Java 풀이

문제 링크

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

프로그래머스

문제 분류

• 정렬
• 그리디
• 배열

문제 요약

길이가 같은 두 배열 A, B가 주어진다.

각 배열에서 숫자를 하나씩 뽑아 서로 곱한 뒤, 그 곱한 값들을 모두 더한다.

이때 각 배열의 원소는 한 번씩만 사용할 수 있다.

최종적으로 만들어지는 누적합이 최소가 되도록 하는 값을 구하는 문제이다.

예를 들어 다음과 같다.

A = [1, 4, 2]
B = [5, 4, 4]

결과 = 29

풀이 아이디어

이 문제의 핵심은 다음과 같다.

작은 값은 큰 값과 곱하고,
큰 값은 작은 값과 곱해야 전체 합이 최소가 된다.

예를 들어 다음과 같은 배열이 있다고 하자.

A = [1, 4, 2]
B = [5, 4, 4]

먼저 두 배열을 오름차순으로 정렬한다.

A = [1, 2, 4]
B = [4, 4, 5]

이제 A는 앞에서부터 작은 값 순서로 사용하고, B는 뒤에서부터 큰 값 순서로 사용한다.

1 × 5 = 5
2 × 4 = 8
4 × 4 = 16

따라서 총합은 다음과 같다.

5 + 8 + 16 = 29

이처럼 한 배열은 작은 값부터, 다른 배열은 큰 값부터 곱하면 곱의 합을 최소로 만들 수 있다.

코드

package programmers.lv2.p12941;

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

import java.util.Arrays;

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

        Arrays.sort(A);
        Arrays.sort(B);

        for (int i = 0; i < A.length; i++) {
            answer += A[i] * B[B.length - 1 - i];
        }

        return answer;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int result1 = solution.solution(
                new int[]{1, 4, 2},
                new int[]{5, 4, 4}
        );

        int result2 = solution.solution(
                new int[]{1, 2},
                new int[]{3, 4}
        );

        System.out.println(result1); // 29
        System.out.println(result2); // 10
    }
}

프로그래머스 제출용 코드

import java.util.Arrays;

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

        Arrays.sort(A);
        Arrays.sort(B);

        for (int i = 0; i < A.length; i++) {
            answer += A[i] * B[B.length - 1 - i];
        }

        return answer;
    }
}

코드 설명

Arrays.sort(A);
Arrays.sort(B);

먼저 Arrays.sort()를 사용해 두 배열을 오름차순으로 정렬한다.

정렬을 하면 각 배열의 작은 값과 큰 값을 쉽게 찾을 수 있다.

---

for (int i = 0; i < A.length; i++) {
    answer += A[i] * B[B.length - 1 - i];
}

반복문은 A.length만큼 실행한다.

문제에서 A와 B의 길이가 같다고 주어졌기 때문에 A.length를 기준으로 반복해도 된다.

---

A[i]

A 배열은 오름차순으로 정렬되어 있으므로 A[i]는 작은 값부터 접근한다.

예를 들어 A = [1, 2, 4]라면 다음과 같이 접근한다.

i = 0 → A[0] = 1
i = 1 → A[1] = 2
i = 2 → A[2] = 4

---

B[B.length - 1 - i]

B 배열은 오름차순으로 정렬되어 있지만, 큰 값부터 사용해야 하므로 뒤에서부터 접근한다.

예를 들어 B.length가 3이라면 다음과 같다.

i = 0 → B[3 - 1 - 0] = B[2]
i = 1 → B[3 - 1 - 1] = B[1]
i = 2 → B[3 - 1 - 2] = B[0]

즉, B 배열을 뒤에서부터 접근하는 구조이다.

---

answer += A[i] * B[B.length - 1 - i];

A의 작은 값과 B의 큰 값을 곱한 뒤 answer에 누적한다.

이 과정을 모든 원소에 대해 반복하면 최종적으로 곱의 합이 최소가 된다.

왜 순서는 상관없을까?

곱셈은 순서가 바뀌어도 결과가 같다.

A의 작은 값 × B의 큰 값

과

B의 큰 값 × A의 작은 값

은 같은 결과이다.

따라서 A와 B 중 어떤 배열에 더 큰 값이 있는지 먼저 찾을 필요는 없다.

중요한 것은 다음 한 가지이다.

한 배열은 작은 값부터,
다른 배열은 큰 값부터 곱한다.

그래서 아래 두 방식 모두 가능하다.

방식 1

answer += A[i] * B[B.length - 1 - i];

방식 2

answer += A[A.length - 1 - i] * B[i];

두 방식 모두 한 배열은 앞에서부터, 다른 배열은 뒤에서부터 접근하는 방식이므로 결과는 같다.

배열을 사용하는 이유

이 문제에서는 처음부터 int[] A, int[] B가 주어진다.

또한 두 배열의 길이가 같다고 문제에서 보장한다.

따라서 값을 새로 추가하면서 크기를 늘릴 필요가 없다.

이런 경우에는 ArrayList를 사용할 필요 없이 배열을 그대로 사용하면 된다.

정리하면 다음과 같다.

상황	사용
길이가 정해져 있는 경우	배열
값을 몇 개 담을지 모르는 경우	ArrayList

length와 length() 차이

Java에서 배열의 길이를 구할 때는 length를 사용한다.

A.length

문자열의 길이를 구할 때는 length()를 사용한다.

str.length()

그리고 ArrayList의 크기를 구할 때는 size()를 사용한다.

list.size()

정리하면 다음과 같다.

대상	사용법
배열	length
문자열	length()
ArrayList	size()

시간복잡도

이 풀이에서는 두 배열을 정렬한다.

Arrays.sort(A);
Arrays.sort(B);

정렬의 시간복잡도는 다음과 같다.

O(n log n)

그 후 반복문을 한 번 실행한다.

O(n)

하지만 전체 시간복잡도에서는 정렬의 시간복잡도가 더 크기 때문에 최종 시간복잡도는 다음과 같다.

O(n log n)

공간복잡도

추가로 새로운 배열을 만들지 않고, 주어진 배열을 정렬해서 사용한다.

따라서 별도의 큰 추가 공간은 사용하지 않는다.

일반적으로 공간복잡도는 다음과 같이 볼 수 있다.

O(1)

단, Arrays.sort() 내부 구현에 따라 정렬 과정에서 일부 추가 공간이 사용될 수 있다.

정리

이 문제는 두 배열의 원소를 하나씩 곱해서 합을 최소로 만드는 문제이다.

핵심은 다음과 같다.

작은 값은 큰 값과 곱하고,
큰 값은 작은 값과 곱한다.

이를 구현하기 위해 두 배열을 오름차순으로 정렬한 뒤, 한 배열은 앞에서부터, 다른 배열은 뒤에서부터 접근하면 된다.

이번 문제를 통해 다음 내용을 정리할 수 있었다.

• 배열 정렬은 Arrays.sort()를 사용한다.
• 배열의 길이는 length로 구한다.
• 문자열의 길이는 length()로 구한다.
• ArrayList의 크기는 size()로 구한다.
• 곱의 합을 최소화하려면 작은 값과 큰 값을 서로 매칭한다.
• 두 배열의 길이가 같다면 하나의 배열 길이를 기준으로 반복문을 작성해도 된다.