[알고리즘/자바스크립트] 트리보나치 수열 구하기 (Tribonacci Sequence)

-해당 문제는 codewars사이트의 level6 문제입니다. (1~8단계 중 8단계가 가장 쉬운 레벨)-

[문제] Well met with Fibonacci bigger brother, AKA Tribonacci.

As the name may already reveal, it works basically like a Fibonacci, but summing the last 3 (instead of 2) numbers of the sequence to generate the next. And, worse part of it, regrettably I won't get to hear non-native Italian speakers trying to pronounce it :(

So, if we are to start our Tribonacci sequence with [1, 1, 1] as a starting input (AKA signature), we have this sequence:

[1, 1 ,1, 3, 5, 9, 17, 31, ...]

But what if we started with [0, 0, 1] as a signature? As starting with [0, 1] instead of [1, 1] basically shifts the common Fibonacci sequence by once place, you may be tempted to think that we would get the same sequence shifted by 2 places, but that is not the case and we would get:

[0, 0, 1, 1, 2, 4, 7, 13, 24, ...]

Well, you may have guessed it by now, but to be clear: you need to create a fibonacci function that given a signature array/list, returns the first n elements - signature included of the so seeded sequence.

Signature will always contain 3 numbers; n will always be a non-negative number; if n == 0, then return an empty array and be ready for anything else which is not clearly specified ;)

If you enjoyed this kata more advanced and generalized version of it can be found in the Xbonacci kata

[Personal thanks to Professor Jim Fowler on Coursera for his awesome classes that I really recommend to any math enthusiast and for showing me this mathematical curiosity too with his usual contagious passion :)]

[해석] 말그대로 트리보나치 수열을 구하는 문제! 피보나치 수열은 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 트리보나치는 피보나치 수열과 거의 같은데 대신 두 항의 합이 아닌 세 항의 합을 구한다.

함수에 초기 숫자 배열인 signature와 n을 넣는데 트리보나치 수열을 n개로 만들어 return시키면 된다.

예를 들어 tribonacci ([1,1,1],10) 함수는 [ 1, 1, 1, 3, 5, 9, 17, 31, 57, 105 ]을 return한다.

tribonacci ([0, 0, 1], 0) => []

tribonacci ([1, 1, 1], 1) => [1]

tribonacci ([0, 1, 1], 5) => [0, 1, 1, 2, 4]

이 문제는 푸는 데 시간이 꽤 걸렸다ㅜㅜ

사실 코드도 그렇게 간단하게 짠 것 같지가 않다.

다른 사람 풀이 보니까 간단한게 짠게 많던데 아직 부족한게 많은듯.

어쨌든 이 문제는 한칸씩 밀어서 계속 3개씩 합하고 그 숫자를 계속 배열 마지막에 추가해야한다는게 핵심이다.

처음에 짠 코드는 아래와 같다.

function tribonacci (signature, n) {
	var num = 0;
	if(n <= 3) {
		return signature.splice(0, n)
	}
	while (num < n-3) {
		var sum=0
		for(var i=num; i<num+3; i++) {
			sum += signature[i]
		}
		signature.push(sum)
		num++;
	}
	return signature
}

일단 num이라는 초기값을 0으로 두었다.

그리고 n이 3보다 작거나 같으면 signature배열을 0부터 그 n번까지 잘라서 return했다.

그래야 n이 3보다 작은 경우에도 불필요하게 for문을 도는 일이 없을테니까.

그리고 for문으로 배열에 있는 숫자를 3개씩 더하면서 반복을 하는데

그 더하는 과정을 n-3번해야한다.

왜 n-3이냐면 초기 배열 요소의 개수가 3이고 거기에 n-3개의 숫자를 추가해서 총 n개의 숫자가 든 배열을 만들어야하기 때문이다.

그리고 sum이란 변수를 주고 signature[i]를 3번 더한 값을 배열에 push()로 추가해준다.

추가되고 난 후 num을 하나씩 증가시켜줌으로서 이 과정을 n-3번 반복한다.

일단 이렇게 짠 코드는 제대로 잘 작동되어 테스트는 통과하였다.

그런데 문제는 코드가 너무 쓸데없이 길다는거!

항상 처음에 짠 코드를 여러 번 잘 읽어보면 불필요한 구석이 있다.

예를들면 while문 안에 for문을 돌린거. 반복을 2번이나 하는 셈인데

생각해보면 무조건 숫자는 3개만 더할거라 굳이 for문을 쓸 필요가 없는 느낌.

function tribonacci (signature, n) {
	if(n <= 3) {
		return signature.splice(0, n)
	}
	for(var i=0; i<n-3; i++) {
		signature.push(signature[i] + signature[i+1] + signature[i+2])
	}
	return signature
}

그렇게 줄이고 줄여서 다시 짠 코드.

for문을 n-3번만큼 돌리고

signature 배열에 signature[i] + signature[i+1] + signature[i+2]를 push해준다.

이렇게 일렬로 쭉 쓰면 될 것을 sum이란 변수를 만들어서 반복을 돌리고 

while문을 써서 num이란 숫자를 ++시켜서 돌리고 할 필요가 없었던 것 같다.

while문은 주로 몇 번 반복할지 확실치 않은 경우에 쓰면 좋다고 배웠는데

이 경우에는 몇 번 반복하는지 확실하게 정해져있으니 for문이 맞는 것 같다.

다시 테스트해봤더니 확실히 아까의 코드보다 속도가 빨라졌다!

짝짝짝