[TIL_37] C# 콜라츠 추측

문제 설명

1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될 때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다.

• 1-1. 입력된 수가 짝수라면 2로 나눕니다.
  1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
• 2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.
     예를 들어, 주어진 수가 6이라면 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 이 되어 총 8번 만에 1이 됩니다. 위 작업을 몇 번이나 반복해야 하는지 반환하는 함수, solution을 완성해 주세요.
• 단, 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 –1을 반환해 주세요.

제한 사항

입력된 수, num은 1 이상 8,000,000 미만인 정수입니다.

나의 시도

public class Solution {
    public int solution(int num) {
        if (num == 1) {
            return 0;
        }
        
        for (int i = 0; i <= 500; i++) { // 500번의 반복 후에도 결과를 찾지 못하면 종료
            if (num == 1) {
                return i; // 1이면 반복 횟수를 반환
            } else if (num % 2 == 0) { // 짝수인 경우
                num /= 2; // 숫자를 2로 나눔
            } else { // 홀수인 경우
                num = num * 3 + 1; // 숫자를 3배하고 1을 더함
            }
        }
        return -1; // 500번의 반복 후에도 결과를 찾지 못하면 -1을 반환
    }
}

이렇게 하면 626331수 에 대한 값을 -1로 못받음. 왜?

찾아보니 626331을 넣으면 overflow가 된다는데.. 626331에 3을 곱해도 21억 초과가 안되니까 overflow 안될텐데..

재시도

public class Solution {
    public int solution(long num) {
        if (num == 1) {
            return 0;
        }
        
        for (int i = 0; i <= 500; i++) { // 500번의 반복 후에도 결과를 찾지 못하면 종료
            if (num == 1) {
                return i; // 1이면 반복 횟수를 반환
            } else if (num % 2 == 0) { // 짝수인 경우
                num /= 2; // 숫자를 2로 나눔
            } else { // 홀수인 경우
                num = num * 3 + 1; // 숫자를 3배하고 1을 더함
            }
        }
        return -1; // 500번의 반복 후에도 결과를 찾지 못하면 -1을 반환
    }
}

뭐 그래도 통과 해야 되니 num을 long으로 받아주는걸로 변경

다른 풀이

public class Solution {
    public int solution(long num) {
        
        // 주어진 수가 1인 경우에는 0을 리턴
        if (num == 1) {
            return 0;
        }
        
        for (int i = 0; i <= 500; i++) { // 500번의 반복 후에도 결과를 찾지 못하면 종료
            num = num % 2 == 0 ? num / 2 : num * 3 + 1;
            if (num == 1) { // 주어진 수가 1이 되면 반복 종료
                return i + 1; // 반복 횟수를 반환하기 위해 i에 1을 더함
            }
        }
        
        return -1; // 500번의 반복 후에도 결과를 찾지 못하면 -1을 반환
    }
}

다른 사람 풀이

public class Solution {
    public int solution(int num) {
        long lNum = num;
        for (int i = 0; i < 500; i++)
        {
            if (lNum == 1) return i;
            lNum = lNum % 2 == 0 ? lNum / 2 : lNum * 3 + 1;                        
        }
        return -1;        
    }
}

간단하게 쓰넹

아 콜라 먹고 싶다..