콜라츠 추측

Posted on Edited on In , ,

문제정의

콜라츠 추측을 몇 번 반복해야 1이 나오는지 계산하는 문제이다. 짝수인 경우 2로 나누고, 홀수인 경우 3을 곱하고 1을 더한다. 500번을 계산해도 1이 안된다면 -1을 반환한다.

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class CollatzGuess {

    //프로그래머스 문제풀이 level1 콜라스 추측
    public static void main(String[] args)
    {
        int num = 6;
        int answer = 0;
        int cnt = 0;
        long ll = num;
        while(cnt <= 500)
        {
            if(ll == 1)
                break;
            else if(ll % 2 == 0)
                ll /= 2;
            else
                ll = ll*3+1;
            cnt++;
        }
        if(cnt <= 500)
            answer = cnt;
        else
            answer = -1;

        System.out.print(answer);

    }
    
}
문제에서 제시한대로 코드를 짜면 된다. cnt를 0으로 초기화하고, 짝수면 나누기, 홀수면 곱하기 더하기 연산을 하면된다. 중요한 부분은 int를 쓰지 않고 long을 쓴 것을 볼 수 있는데, 이유는 곱하기 연산을 하면서 int값을 초과할 수 있기 때문이다. 필자는 이것 때문에 한번 틀렸었다. 이 문제 정의에서 이 알고리즘의 시간복잡도는 \(O(1)\)이다. 왜냐하면 500이라는 횟수가 최대 실행 횟수이기 때문이다.

테스트