Post

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

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

문제 링크


1. 아이디어

현재 값 $x$가 짝수면 2로 나누고 홀수면 $3x + 1$로 바꾸는 과정을 따라가며 거친 값을 기록하는 시뮬레이션이다. 시작값 $n$이 1000 이하이면 1에 도달하는 것이 알려져 있어 반복은 반드시 끝난다. 1도 수열에 들어가므로 1이 되기 전까지만 돌리고 1은 마지막에 붙인다.


2. 코드

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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;
}
1
2
3
4
5
6
7
8
9
10
11
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

This post is licensed under CC BY 4.0 by the author.