(프로그래머스) 최저값 작성(Java)

  • by

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

프로그래머스

코드 중심 개발자 채용. 스택 기반 포지션 매칭 프로그래머스 개발자를 위한 커스텀 프로파일을 등록하고 나와 기술의 궁합이 잘 맞는 기업을 매칭합니다.

programmers.co.kr

인기글

문제 설명

같은 길이의 배열 A, B의 두 가지가 있습니다.

각 배열은 자연수로 구성됩니다.


배열 A, B에서 각각 하나의 숫자를 빼고 두 개의 숫자를 곱합니다.

이 프로세스를 배열의 길이만큼 반복하고 두 개의 숫자를 곱한 값을 누적하여 더합니다.

이때 최종적으로 누적된 값을 최소화하는 것이 목표입니다.

(단, 각 배열에서 k번째 숫자를 선택한 경우에는 k번째 숫자를 다시 당길 수 없습니다.

)

예를 들어 A = (1, 4, 2) B = (5, 4, 4) 라면

  • A에서 첫 번째 숫자인 1, B에서 첫 번째 숫자인 5를 뺀 다음 곱하고 가산합니다.

    (누적값: 0+5(1×5)=5)
  • A에서 2번째 숫자인 4, B에서 3번째 숫자인 4를 빼서 곱하고 가산합니다.

    (누적값: 5+16(4×4)=21)
  • A에서 3번째 숫자인 2, B에서 2번째 숫자인 4를 빼서 곱하고 가산합니다.

    (누적값: 21+8(2×4)=29)

즉, 이 경우는 최소화되기 때문에 29를 반환합니다.

배열 A, B 가 주어졌을 때에 최종적으로 누적된 최저치를 return 하는 solution 함수를 완성해 주세요.

제한사항

  • 배열 A, B 크기: 1,000 이하의 자연수
  • 배열 A, B의 원소 크기: 1,000 이하의 자연수
입출력 예

A B answer
(1, 4, 2) (5, 4, 4) 29
(1,2) (3,4) 10

문제 해결 계획

1. 배열을 각각 오름차순, 내림차순으로 정렬

2. 배열의 길이만큼 각 배열의 값을 곱하여 answer에 추가

1차 시도

import java.util.*;
class Solution {
    public int solution(int ()A, int ()B) {
        int answer = 0;
            Arrays.sort(A);
            Integer() C = Arrays.stream(B).boxed().toArray(Integer()::new);
            Arrays.sort(C, Collections.reverseOrder());
            
            for ( int i = 0; i < A.length; i++) {
                answer += A(i)*C(i);
            }
            
            return answer;
    }
}


Arrays 함수에 내림차순 정렬이 없으므로 어쨌든 내림차순 정렬을 수행했는데 효율 테스트에서 시간 초과가 발생했습니다.

2차 시도

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 - i - 1);
            }

            return answer;
    }
}

배열 2개 모두 오름차순으로 나란히 배열 1개는 공식적으로 내림차순으로 했다

결과는 통과