[Programmers] #181919 - 콜라츠 수열 만들기 [Java][C++][Python]

문제 링크

---

1. 아이디어

n이 1보다 큰 동안 짝수면 2로 나누고 홀수면 $3n + 1$로 바꾸는 과정을 그대로 반복하면서, 매 단계의 n 값을 결과 배열에 순서대로 기록한다. n ≤ 1,000 범위에서는 이 과정이 항상 유한 횟수 안에 1로 수렴함이 알려져 있으므로, 별도의 종료 조건 없이 반복문 조건(n > 1)만으로 안전하게 끝난다. 반복이 끝나는 시점의 n(= 1)은 아직 배열에 담기지 않았으므로, 반복문을 빠져나온 뒤 마지막으로 한 번 더 추가한다.

---

2. 복잡도

접근	시간	공간
풀이	$O(K)$	$O(K)$

($K$ = n에서 시작하는 콜라츠 수열의 길이)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public int[] solution(int n) {
        List<Integer> list = new ArrayList<>();
        while (n > 1) {
            list.add(n);
            if (n % 2 == 1) {
                n = 3 * n + 1;
            } else {
                n /= 2;
            }
        }
        list.add(n);

        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(int n) {
    vector<int> v;
    while (n > 1) {
        v.push_back(n);
        if (n % 2) {
            n = 3 * n + 1;
        } else {
            n /= 2;
        }
    }
    v.push_back(n);

    return v;
}

def solution(n):
    ans = []
    while n > 1:
        ans.append(n)
        if n % 2 == 1:
            n = 3 * n + 1
        else:
            n //= 2
    ans.append(n)

    return ans

---