해당 포스팅은 릿코드 202번 Happy Number 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였으며 스택으로 풀었다.
문제
Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.
풀이
input으로 전달받은 숫자의 각 자릿수를 제곱한 후 1이 나올 때까지 더해주는 작업을 반복한다. 이 과정의 결과값이 1이라면 true를, 나올 수 없는 숫자라면 false를 리턴한다.
1이 나올 수 있는 숫자라면 변환 과정 중 나오는 숫자들이 전부 달라야한다. 그 이유는 각 자릿수를 제곱하고 더하는 과정에서 기존에 나왔던 숫자(ex. 14)가 나온다면 그 전의 숫자(14)와 이번에 나온 숫자(14)까지의 변환과정을 다시 반복하기 때문이다.
따라서 stack을 생성 후 반복문을 돌리면서 현재 변환값이 stack에 존재하면 false를 리턴하자.
전체 코드
/**
* @param {number} n
* @return {boolean}
*/
var isHappy = function(n) {
const stack = [];
stack.push(divide(n));
while (true) {
const f = stack[stack.length - 1];
const n = divide(f);
if (n === 1) return true;
if (stack.includes(n)) return false;
stack.push(n);
}
};
function divide(n) {
const nums = String(n).split("");
const sum = nums.reduce((pre, cur) => {
const squared = Math.pow(Number(cur), 2);
return pre += squared;
}, 0)
return sum;
}