[12943] 콜라츠 추측

✔ 콜라츠 추측

[프로그래머스 12943]

문제 분석하기

입력된 수가 짝수인지, 홀수인지에 따라 반복하여 500번 안에 1을 만들 수 있다면 인덱스를 반환, 그렇지 않다면 -1을 반환하도록 함

손으로 풀어보기

1. 입력된 수를 long형으로 저장
   • 3을 곱할 경우 int형 범위를 넘어 오버플로우가 발생할 수 있음
2. 입력된 수가 짝수인지, 홀수인지에 따라 반복하며 인덱스를 증가시킴
3. 500번 안에 1을 만들 수 있다면 인덱스를 반환
4. 그렇지 않다면 -1을 반환

슈도코드 작성하기

num(주어진 수)
n(num을 long형으로 변환한 수)
index(인덱스)
while(index < 500) {
    if(n이 1이라면)
        index 반환
    else if(n이 짝수라면)
        n = n / 2
    else
        n = n * 3 + 1
    index 증가
}
500번 반복할 때까지 1이 되지 않는다면 –1을 반환

코드 구현하기

/**
 * 12943) 콜라츠_추측
 */
public class L025_12943 {
    // num(주어진 수)
    public int solution(int num) {
        // n(num을 long형으로 변환한 수)
        long n = (long) num;
        // index(인덱스)
        int index = 0;
        // index가 500번보다 작을 동안
        while (index < 500) {
            // n이 1이라면
            if (n == 1)
                // index 반환
                return index;
            // n이 짝수라면
            else if (n % 2 == 0)
                n = n / 2;
            // n이 홀수라면
            else
                n = n * 3 + 1;
            // index 증가
            index++;
        }
        // 500번 반복할 때까지 1이 되지 않는다면 –1을 반환
        return -1;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L025_12943 solution = new L025_12943();

        int num = 626331;

        int result = solution.solution(num);

        System.out.println(result);
    }
}