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

문제 링크

---

1. 아이디어

반복문을 활용해 n이 1보다 큰 동안 짝수면 $2$로 나누고 홀수면 $3n + 1$로 바꾸는 과정을 반복하면서, 매 단계의 n 값을 결과 배열에 순서대로 기록하면 된다. 반복문을 탈출하는 순간은 n이 1인 경우 하나로 배열의 마지막에 1만 추가로 삽입해서 반환하면 된다.

---

2. 복잡도

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

($K$ = 콜라츠 수열의 길이)

---

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 != 0) {
                n = 3 * n + 1;
            } else {
                n /= 2;
            }
        }
        list.add(1);

        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(1);

    return v;
}

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

    return ans

---