이 글은 js 자바스크립트 알고리즘 강의를 듣고 배운점을 기록한 게시글 입니다.
1.완전탐색 (자릿수의 합)
문제:N개의 자연수가 입력되면 각 자연수의 자릿수의 합을 구하고, 그 합이 최대인 자연수를 출력하는 프로그램을 작성하세요.
자릿수의 합이 같은 경우 원래 숫자가 큰 숫자를 답으로 합니다.
만약 235 와 1234가 동시에 답이 될 수 있다면 1234를 답으로 출력해야 합니다.
코드
function sol(arr) { let answer = 0; let max = Number.MIN_SAFE_INTEGER; for (let x of arr) { let sum = 0, tmp = x; while (tmp) { sum += tmp % 10; tmp = Math.floor(tmp / 10); } if (sum > max) { max = sum; answer = x; } else if (sum === max) { if (answer < x) { answer = x; } } } return answer; } let arr = [128, 460, 603, 40, 521, 137, 123]; console.log(sol(arr));
자릿수의 합 문제 풀이
이 문제는 자연수가 입력되면 자릿수의합 (100의 자리,10의자리,1의자리) 을 구하여 , 최댓값을 가진 자연수를 구하는 문제입니다. 자릿수의 합이 같은 경우 숫자를 비교하여 더 큰 자연수가 답이 되는 문제 입니다.
먼저 자연수의 합을 구하기 위해서는 두가지 방법이 있습니다.
1.reduce 내장함수를 이용하여 sum을 추출해내는 방법
2.while 문을 통해서 sum 을 추출해내는 방법이 있습니다.
while 문을 통해 sum을 추출해내보도록 하겠습니다.
수학적인 공식이 있는데, 128을 10으로 나누면 앞자리 수는 몫이 되고 , 뒷자리 수는 나머지가 됩니다.
128을 10으로 나누면 12가 몫이되고, 8이 나머지가 됩니다. 이 공식을 이용해서 코드를 짯습니다.
while (tmp) {
sum += tmp % 10;
tmp = Math.floor(tmp / 10);
}
이렇게 하게 되면 sum은 128을 10으로 나눈 값이 누적 될거고 tmp는 몫이 됩니다.
tmp가 0이 될때까지 while문이 돌기 때문에 몫이 0이 되기전까지의 나머지의 합이 sum에 누적 됩니다.
sum을 구했다면? sum이 가장 큰 자연수를 찾는 일을 해야 합니다.
앞에서 먼저 선언했던 변수인 max를 활용해서 가장 큰 sum이 몇인지를 찾을 수 있습니다.
if(max < sum) max= sum --- 이렇게 하면 가장 큰 sum이 나올때마다 max를 sum 으로 최신화 시켜주고 answer =x(가장 큰 sum의 자연수) 를 넣어줍니다.
여기까지 하게 되면 128이라는 숫자가 가장 큰 값으로 나오게 됩니다.
다만 조건에서 자연수 자릿수의 합이 가장 큰 자연수가 중복 된다면 가장 큰 자연수를 출력하도록 했기 때문에 가장 큰 자연수가 무엇인지 판별해주는 식이 필요합니다.
else if(max === sum) max 와 sum이 같다면?
if(answer < x) answer =x 기존의 x와 새로운 x를 비교하여 answer에 x를 최신화 시켜줍니다.
