콜라츠 추측(Collatz Conjecture)이란?
로타르 콜라츠(Lothar Collatz)가 1937년에 제기한 추측. 페르마의 마지막 정리와 같이 수학자들을 고민에 빠트린 전설의 문제이다. “우박수”, “우박 수열”, “울람 추측”, “카쿠타니 문제”, “하세 알고리즘”, “시라쿠사 문제”, “3N + 1” 등으로 불리기도 한다. 프로그래머스의 문제에서는 콜라츠 수열이라고 표현했다.
콜라츠 추측의 공식
이 함수 T(n)을 모든 자연수 n에 대해 유한번 재귀 반복하면 1로 간다는 추측이다. 풀어서 설명해보면 1을 제외한 아무 자연수를 선택한 다음, 홀수라면 3을 곱한 다음 1을 더하고, 짝수라면 2로 나눈다. 이 과정을 계속 바복하다가 보면 마지막에 1이 나온다 추측이다. 예를 들어 7에서 시작하면 다음과 같은 과정을 거친다.
프로그래머스 콜라츠 수열 자바로 풀이
문제
모든 자연수 x에 대해서 현재 값이 x이면 x가 짝수일 때는 2로 나누고, x가 홀수일 때는 3 * x + 1로 바꾸는 계산을 계속해서 반복하면 언젠가는 반드시 x가 1이 되는지 묻는 문제를 콜라츠 문제라고 부릅니다. 그리고 위 과정에서 거쳐간 모든 수를 기록한 수열을 콜라츠 수열이라고 부릅니다.
계산 결과 1,000 보다 작거나 같은 수에 대해서는 전부 언젠가 1에 도달한다는 것이 알려져 있습니다. 임의의 1,000 보다 작거나 같은 양의 정수 n이 주어질 때 초기값이 n인 콜라츠 수열을 return 하는 solution 함수를 완성해 주세요.
제한사항
1 ≤ n ≤ 1,000
입출력 예
| n | result |
|---|---|
| 10 | [10, 5, 16, 8, 4, 2, 1] |
입출력 설명
| 연산 횟수 | x(연산 결과) | 홀짝 여부 |
|---|---|---|
| 0 | 10 | 짝수 |
| 1 | 5 | 홀수 |
| 2 | 16 | 짝수 |
| 3 | 8 | 짝수 |
| 4 | 4 | 짝수 |
| 5 | 2 | 짝수 |
| 6 | 1 | 홀수 |
따라서 [10, 5, 16, 8, 4, 2, 1]을 return 합니다.
과정을 일렬로 나열해 본다면 아래와 같습니다.
모든 연산 과정을 배열에 담고 이 배열을 리턴하는 함수를 완성해야 합니다.
프로그래머스 콜라츠 수열 자바로 풀이
import java.util.ArrayList;
import java.util.List;
class Solution {
public int[] solution(int n) {
List<Integer> list = new ArrayList<>();
list.add(n);
while(n != 1) {
if (n % 2 == 0) {
n = n / 2;
list.add(n);
continue;
}
if (n % 2 != 0) {
n = n * 3 + 1;
list.add(n);
}
}
return list.stream()
.mapToInt(Integer::intValue)
.toArray();
}
}
프로그래머스의 콜라츠 수열 만들기를 Java로 풀었습니다. 먼저 배열의 크기를 짐작할 수 없기 때문에 ArrayList를 통해서 컬렉션 객체를 생성합니다. 그 후 가장 초기 숫자인 n을 list에 저장합니다.
while 구문을 통해서 n ≠ 1 일 경우에만 동작하며, n이 1에 도달하면 while 구문은 멈추게 됩니다. n이 짝수이면 n을 2로 나누고 list에 저장합니다. n이 홀수이면 n x 3 + 1으로 계산하고, list에 저장합니다.
while 구문이 끝났을 때, ArrayList의 stram을 사용하여 각각의 int 값을 모두 배열에 저장하여 return하게 됩니다.
여기까지 간단하게 프로그래머스의 콜라츠 수열 만들기를 자바로 풀이해보았습니다.
🏷️이미지 출처 및 참고한 사이트
Uploaded by N2T