[프로그래머스/Level2] 최솟값 만들기

문제

https://programmers.co.kr/learn/courses/30/lessons/12941?language=java 

코딩테스트 연습 - 최솟값 만들기

 

풀이

문제 조건

• 길이가 같은 배열 A, B에서 각각 숫자리 하나씩 뽑아 곱한다.
• 위 작업을 배열의 길이 만큼 반복, 곱한 값을 누적해서 더한다.
• 최종적으로 누적된 값이 모든 경우의 수 중 최소가 되게 하라.
• 이미 사용한 위치의 값은 다시 사용할 수 없다.

서로 다른 수를 가진 두 배열 A, B에서 요소들을 곱해 더한 결과가 최솟값이 되기 위해서는 최솟값 x 최댓값으로만 A x B 연산이 수행되어야 한다. 즉 A배열에서 가장 작은 값과 B배열에서 가장 큰 값을 추출해 곱하여 더해야만 최솟값이 될 수 있다. (A배열에서 가장 큰 값과  B배열에서 가장 큰 값이 곱해지면 최종 결과 값이 비교도 안되게 커지게 되므로 이 경우를 막아야 최솟값이 될 수 있음) 물론 반대로 A배열에서 가장 큰 값과 B배열에서 가장 작은 값을 차례로 추출해 곱하여 더하여도 똑같이 최솟값을 얻을 수 있다.

테스트케이스1로 확인해 보자.

A	B	answer
[1, 4, 2]	[5, 4, 4]	29

[A배열에서 가장 작은 값 x B배열에서 가장 큰 값]

• 1 x 5 = 5 / 누적 5
• 2 x 4 = 8 / 누적 13
• 4 x 4 = 16 / 누적 29 → 29

 

[A배열에서 가장 큰 값 x B배열에서 가장 작은 값]

• 4 x 4 = 16 / 누적 16
• 2 x 4 = 8 / 누적 24
• 1 x 5 = 5 / 누적 29 → 29

 

위에서 확인할 수 있듯이 최솟값을 만들기 위한 연산과정에서 A배열은 값이 작은 순으로 연산에 사용되며, B배열은 값이 큰 순으로 연산에 사용된다. 한마디로 A배열은 오름차순으로, B배열은 내림차순으로 정렬한 상태에서 각 요소를 순서대로 곱하여 더하면 위와 같은 결과를 낼 수 있다.

 

1. Arrays.sort() 메서드를 사용해 배열을 각각 오름차순, 내림차순으로 정렬한다.
2. 오름차순은 바로 정렬할 수 있으나, int[] 타입에서는 내림차순 정렬을 바로 할 수 없기 때문에 스트림으로 배열을 Integer[] 타입으로 캐스팅한 후 내림차순 정렬한다.
3. 배열의 길이가 같기 때문에 처음부터 마지막 요소까지 하나씩 곱한 결과를 answer에 누적 저장한다.

 

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

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

        // 오름차순 정렬
        Arrays.sort(A);

        // 내림차순 정렬
        Integer[] BB = Arrays.stream(B).boxed().toArray(Integer[]::new);
        Arrays.sort(BB, Collections.reverseOrder());

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

        return answer;
    }
}

 

바로 성공할 줄 알았으나, 효율성 테스트에서 시간초과로 실패가 뜬다.

 

아마 내림차순 정렬을 위해 int[] 타입을 Integer[] 타입으로 캐스팅하는 과정에서 스트림변환, 박싱, 배열 변환 등 부가적인 작업에 시간이 소모되어 실패가 뜬 것 같다. 스트림을 사용하지 않고 int[] 타입 그대로 사용하는 방식을 생각해본 결과, 두 배열의 정렬 순서와 상관없이 한 배열은 작은 수 부터 연산에 사용하고, 나머지 배열은 큰 수 부터 연산에 사용하면 된다는 걸 깨달았다.

두 배열을 모두 오름차순 정렬한 뒤, A배열은 앞 요소부터 접근 하고 B배열은 뒷 요소부터 접근하는 방식으로 코드를 수정하였다.

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;
    }
}

 

효율성 테스트를 모두 통과하였다.

B배열 요소의 뒤부터 접근할 때 B[B.length - i] 로 해버리면 처음 반복에서 i=0 이기 때문에 B[B.length] 요소에 접근하게 되는데 길이가 B.length인 배열은 인덱스가 [0] ~ [B.length-1] 까지 밖에 없기 때문에 ArrayIndex 에러가 발생하게 된다.