Algorithm/문제
programmers. 최솟값 만들기
Yuclid
2021. 6. 23. 18:00
문제
코딩테스트 연습 - 최솟값 만들기
길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱
programmers.co.kr
풀이
두 개의 배열에서 하나씩 꺼내서 곱해서 누적합을 구한 뒤 가장 작은 값을 구하는 문제
큰 수와 작은 수를 곱해야 작은 수를 구할 수 있다는 발상에서 시작해서
가장 큰 수 * 가장 작은 수
+
두 번째로 큰 수 * 두 번째로 작은 수
+
...
로 가장 작은 누적합을 구할 수 있다
배열 하나는 오름차순 나머지 하나는 내림차순으로 정렬하여서 곱해주면 시간복잡도도 줄일 수 있다
코드
function solution(A,B){
var answer = 0;
A.sort((a, b) => a-b);
B.sort((a, b) => b-a);
for(let i=0; i<A.length;i++){
answer += A[i]*B[i];
}
return answer;
}