문제링크
문제
Task
Given an array of integers , Find the minimum sum which is obtained from summing each Two integers product .
Notes
- Array/list will contain positives only .
- Array/list will always has even size
Input >> Output Examples
minSum({5,4,2,3}) ==> return (22) - Explanation:
The minimum sum obtained from summing each two integers product , 5x2 + 3x4 = 22
minSum({12,6,10,26,3,24}) ==> return (342)- Explanation:
The minimum sum obtained from summing each two integers product , 26x3 + 24x6 + 12x10 = 342
minSum({9,2,8,7,5,4,0,6}) ==> return (74)- Explanation:
The minimum sum obtained from summing each two integers product , 9x0 + 8x2 +7x4 +6x5 = 74
🚩 문제간단해석
배열의 2개씩 곱해서 더한 총합 중 가장 작은 수를 구하시오
예시를 보면 정확히 알 수 있다
문제 접근
function minSum(arr) {
const newArr = arr.sort((a,b)=>a-b);
let minsum = 0;
for(let i = 0; i < newArr.length/2; i++){
minsum += (newArr[i] * newArr[newArr.length-1-i]);
}
return minsum;
}어떻게 곱해야 가장 작은 수를 만들 수 있을까? 이 부분이 문제의 포인트인 것 같다. 임의의 두 수를 뽑아서 곱할 때, 가장 작은 수가 되려면 가장 큰 수와 가장 작은 수를 뽑아서 곱하면 두 수의 곱 중 가장 작은 수가 된다.그 다음 작은 수는 두번째로 큰 수와 두번째로 작은 수를 곱하면 두번째로 작은 두 수의 곱이 된다. 이렇게 순서대로 뽑아서 곱한 수를 더하게 되면 두 수를 뽑아서 곱한 수의 총합 중에서 가장 작은 수가 된다.
이를 구현하기 위해선 먼저 정렬을 해야한다. (오름차순)정렬을 하게 되면, 가장 작은 수인 i=0부터 순서대로, 작은 큰 수인 i=arr.length-1의 역순으로 접근하여 두 수를 곱할 수 있다. 이 때 딱 배열의 반만 순회하면 된다. 한 번 순회시 배열에서 두 개의 요소에 접근해서 곱하기 때문이다.
Best Solution
function minSum(arr) {
return arr.sort( (a,b) => a-b )
.slice(0, arr.length/2)
.reduce( (acc,curr,index) => acc += curr * arr[ arr.length - index - 1 ], 0 )
}내 풀이는 for문을 사용했지만, 여기선 배열 메소드를 통해서 해결하였다. slice()를 통해서 원하는 배열만큼만 만든 후 그 배열을 순회하여 누적값을 구하였다.
메소드체이닝을 해서 풀어보려고 했는데 잘 안되었던 이유가 내가 원하는 만큼만 배열을 순회시킬 수 없어서였다. 그 부분을 slice()를 통해서 해결하였다.
function minSum(arr) {
arr.sort((x,y)=>x-y)
s=0
while(arr.length)s+=arr.pop()*arr.shift()
return s
}메소드를 자유자재로 사용한 풀이라고 생각한다. 정렬 후 배열의 앞에서 하나를 가져오고, 뒤에서 하나를 가져와서 곱하는 것을 반복하였다. pop()과 shift()는 원배열을 변화시키기 때문에 while()문이 진행됨에 따라서 arr.length는 줄어들게 되고 마지막 순회를 마치면 arr.length = 0이 되기 때문에 0은 falsy value로서 while()문을 빠져나오게 된다.
결론
이 문제는 Array Series의 첫번째 문제이다. 이 시리즈를 몇 개 더 풀어보고 괜찮은 문제는 포스팅해봐야겠다. Codewars의 장점은 카테고리(여기선 tag)가 다양하다는 점이다. 보통 알로리즘 이름별로 카테고리를 나누는 경우가 많은데, 여기선 어떤 프로그래밍의 개념이나 분야로 나누는 경우도 있다. 예를 들어 게임이나 퍼즐 카테고리도 있고 버그수정인 보안관련 문제들도 있고 위 문제는 Array관련 문제에 속해있었다. 랜덤으로 주어지는 문제가 아닌 직접 풀고 싶은 문제를 서칭하는 재미도 있는 것 같다.
결론은 Codewars 강추👍👍😎😎
