[프로그래머스] 콜라츠 추측

콜라츠 추측: 자바로 풀어보는 상세 가이드

문제 이해

콜라츠 추측은 간단한 규칙을 가진 수열 문제입니다. 주어진 숫자에 대해 다음 연산을 반복하면 모든 숫자가 결국 1이 된다는 추측입니다.

• 짝수: 2로 나눔
• 홀수: 3을 곱하고 1을 더함

이 문제에서는 주어진 숫자가 1이 되기까지 몇 번의 연산이 필요한지를 구하는 것이 목표입니다.

자바 코드 구현

public int solution(long num) {
    int count = 0;
    while (num != 1 && count < 500) {
        num = num % 2 == 0 ? num / 2 : num * 3 + 1;
        count++;
    }
    return count < 500 ? count : -1;
}

코드 설명

1. count 변수: 연산 횟수를 세기 위한 변수입니다.
2. while 루프: num이 1이 아니고 count가 500보다 작을 때까지 반복합니다.
3. 짝수/홀수 판별 및 연산: 삼항 연산자를 이용하여 짝수와 홀수에 따른 연산을 간결하게 표현합니다.
4. 반환값: 500번 이내에 1이 되면 count를 반환하고, 아니면 -1을 반환합니다.

핵심 포인트

• long형 사용: 매우 큰 수가 발생할 수 있으므로 int 대신 long형을 사용하는 것이 좋습니다.
• 반복문 종료 조건: num이 1이 되거나 500번을 초과하면 반복을 종료합니다.
• 삼항 연산자: 짝수/홀수 판별과 연산을 간결하게 표현합니다.

시간 복잡도

• 최악의 경우: 주어진 수가 1이 되기까지 500번의 연산을 모두 수행해야 하는 경우입니다. 따라서 시간 복잡도는 O(1)로 볼 수 있습니다. 즉, 입력값의 크기에 상관없이 일정한 시간이 소요됩니다.
• 평균적인 경우: 콜라츠 추측은 아직 증명되지 않았기 때문에 정확한 평균 시간 복잡도를 계산하기는 어렵습니다. 하지만 많은 실험 결과를 통해 대부분의 수는 비교적 빠르게 1로 수렴하는 경향을 보입니다.

하지만 주의해야 할 점은, 콜라츠 추측은 모든 수에 대해 유한번의 연산 후 1로 수렴한다는 것이 증명되지 않았기 때문에, 최악의 경우 무한 루프에 빠질 가능성도 있다는 것입니다.

공간 복잡도

• 추가 메모리 사용: 알고리즘 실행 과정에서 사용되는 변수는 num과 count 두 개뿐입니다.
• 공간 복잡도: 따라서 공간 복잡도는 O(1)로, 입력값의 크기에 상관없이 일정한 메모리 공간만을 사용합니다.

개선점 및 추가 고려 사항

• 코드 가독성: 변수명을 더 명확하게 하고, 주석을 추가하여 코드 이해도를 높일 수 있습니다.
• 효율성: 비트 연산을 이용하여 짝수/홀수 판별을 더 빠르게 수행할 수 있습니다.
• 다른 풀이: 재귀 함수를 이용하거나 동적 계획법을 적용하여 다른 방식으로 문제를 해결할 수 있습니다.