[Programmers] 콜라츠 수열 만들기

mori·2024년 8월 23일

Problem 💻

문제

모든 자연수 x에 대해서 현재 값이 x이면 x가 짝수일 때는 2로 나누고, x가 홀수일 때는 3 * x + 1로 바꾸는 계산을 계속해서 반복하면 언젠가는 반드시 x가 1이 되는지 묻는 문제를 콜라츠 문제라고 부릅니다.

그리고 위 과정에서 거쳐간 모든 수를 기록한 수열을 콜라츠 수열이라고 부릅니다.

계산 결과 1,000 보다 작거나 같은 수에 대해서는 전부 언젠가 1에 도달한다는 것이 알려져 있습니다.

임의의 1,000 보다 작거나 같은 양의 정수 n이 주어질 때 초기값이 n인 콜라츠 수열을 return 하는 solution 함수를 완성해 주세요.

입출력

n	result
10	[10, 5, 16, 8, 4, 2, 1]

출력 예시

예제 1

연산 횟수	x	홀짝 여부
0	10	짝수
1	5	홀수
2	16	짝수
3	8	짝수
4	4	짝수
5	2	짝수
6	1	홀수

따라서 [10, 5, 16, 8, 4, 2, 1]을 return 합니다.

Approach

알고리즘

콜라츠 수열

의문점

while을 사용하는 이유
```
while (current !== 1) {
  // current가 1이 아닌 동안, 즉 1이 될 때까지 계속 반복
}
```
- 다른 반복문(for, do…while)도 가능하지만 while문은 조건에 따라 반복을 수행하는 상황에서 매우 직관적이고 간단하게 코드 작성이 가능하다.
- while문 : 반복 횟수가 불확실할 때 / 반복이 특정 조건에 의해 언제 끝날지 모를 때 사용
- for문 : 반복 횟수가 명확하거나 반복 회수를 알고 있는 경우 사용
콜라츠 수열 마지막은 무조건 1
```
result.push(1);
```
- 반복문이 끝나면 1 꼭 넣어주기!

요약

콜라츠 수열은 종료 조건이 명확하기 때문에 while 반목문을 사용하자!

Solution 💡

내 코드

function solution(n) {
    const result = [];
    while(n !== 1) {
        result.push(n);
        if(n%2 === 0) {
            n = n/2;
        } else {
            n = 3*n+1
        }
    }
    result.push(1);
    return result;
}

남 코드

function solution(n, arr = []) { 
    arr.push(n) //현재 숫자n을 배열에 추가 => 이후 재귀 호출이 진행되며 다음 숫자들이 차례대로 배열에 추가
    if (n === 1) return arr  //종료 조건
    if (n % 2 === 0) return solution(n / 2, arr)  //재귀호출: 짝수처리 => 짝수인지 확인 후 다시 solution 호출
    return solution(3 * n + 1, arr) //재귀호출: 홀수처리
}

재귀함수 : 자기 자신을 호출하는 함수 / 장점 : 반복적인 계산을 간결하게 표현 가능
각 재귀호출마다 숫자가 갱신되어 콜라츠 수열이 완성

처음으로 만난 콜라츠 문제! 콜라츠에 대해 잘 기억해두자 😀