[알고리즘/자바스크립트] 약수 구하는 알고리즘 (Find the divisors!)

오늘부터 시간이 날 때마다 https://www.codewars.com/의 알고리즘 문제들을 풀어보고 

문제를 풀며 나의 굳은 뇌를 쥐어짜는 과정에서 우러나오는 온갖 고뇌를 글로 적어보려고 한다...

알고리즘 서적을 찾아보면 죄다 파이썬이나 자바 기반으로 되어있는데

난 내가 할 줄 아는 자바스크립트로 풀어볼 예정이다.

codewars는 해외 사이트라 문제가 죄다 영어다.

한국에도 프로그래머스라는 유명한 알고리즘 사이트가 있는데 문제는

이노무 프로그래머스에서 문제 푸는 사람들을 죄다 천재로 보는건지

문제 수준이 너무 높다.

분명 레벨1이라고 해서 즐거운 마음으로 문제를 읽었는데

문제 읽는데만 5분 해석하는데 10분 문제 푸는 데 하루가 소요되는 기적...

문제의 수도 해외 사이트에 비해 적을 뿐더러

레벨도 전반적으로 너무 높은 느낌이라

나같은 초보자가 접하면 와아~ 때려쳐야지~ 하고 창을 닫게 된다;;

그래서 일단 문제 수도 많고 레벨도 1~8단계까지 다양한 codewars의 문제를 풀어보기로 했다.

(아래 문제는 7단계 문제입니다.)

--------------------------------

[문제] Create a function named divisors/Divisors that takes an integer n > 1 and returns an array with all of the integer's divisors(except for 1 and the number itself), from smallest to largest. If the number is prime return the string '(integer) is prime' (null in C#) (use Either String a in Haskell and Result<Vec<u32>, String> in Rust).

Example:

divisors(12); // should return [2,3,4,6]

divisors(25); // should return [5]

divisors(13); // should return "13 is prime"

---------------------------------

오우, 영어라 괜히 읽기 싫어지지만 영어사전과 함께 차분히 읽어보니 이렇다.

[해석] divisiors 또는 Divisiors라는 이름의 함수를 만들어라.

1보다 큰 수의 integer가 파라미터인데 얘의 약수를 구해라.

약수를 구해서 그 약수들을 오름차순 배열로 만들어서 return시켜라.

근데 1과 자기 자신은 제외하고 배열로 만들어라.

약수가 없는 수는 '해당 숫자' is prime이라는 문구를 return해라.

호우~ 약수 초딩 때 배웠는데 약수..가 뭐지....흑흑..

일단 여기서부터 막혀서 급하게 구글에 검색하니..

어떤 숫자 예를 들면 12라는 숫자가 있다고 쳐보자.

그 12를 2로 나눴을 때 나머지가 없이 깔끔하게 나눠지면 그 2는 12의 약수가 된다.

즉, 어떤 수로 나눴을 때 나머지가 0이 되는 수가 약수이다.

그러니까 12의 약수는 2, 3, 4, 6이 되는거다.

오호 그건 잘 알겠는데 그걸 함수로 어떻게 만들지.... 산넘어 산이다.

잘 생각해보자. 

12의 약수가 되려면 나눗셈했을 때 나머지가 0이 되야한다.

그걸 코드로 표현하면 12 % n == 0 이 되면 n은 12의 약수가 된다는 뜻이다.

근데 일단 1과 자기 자신을 제외하랬으니

12를 2부터 11사이의 숫자들로 나눠본 후 0이 되는 숫자를 찾으면 된다는 거다!

여기까지 생각이 가니까 바로 감이 왔다.

function divisors(integer) {
    for(var i=2; i<integer; i++) {
        if(integer % i == 0) {
            console.log(i)
        }
    }
}
divisors(12);

1을 제외하랬으니 i=2부터 12보다 작을때까지 for문을 돌려서

12 % i 가 0이면 i를 출력해봤더니

12의 약수 2, 3, 4, 6이 차례로 출력되었다.

function divisors(integer) {
	var arr = [];
	for(var i=2; i<integer; i++) {
		if(integer % i == 0) {
			arr.push(i);
		}
	}
	if(! arr[0]) {
		return integer + ' is prime'
	} else {
		return arr
	}
}
console.log(divisors(12));
console.log(divisors(13));

이제 빈 배열을 만들고 약수를 배열에 push한다.

그리고 배열의 0번째 요소가 빈값이라면 undefined가 되어 (! arr[0])에서 true가 될테니

integer + 'is prime'을 return하고

반대의 경우에는 arr를 return한다.

이렇게 쓰고 답안을 제출하니

짝짝짝! 통과했다.