[알고리즘] 콜라츠 추측

문제 요구사항

1차 풀이(결과 : 실패)

class Solution {
    public int solution(int num) {
        if(num == 1) return 0; 
        for(int i = 0;i < 500;i++){
            if(num%2==0) {
                num /= 2;
                continue;
            }
            else if(num!=1){
                num = num*3 + 1;
                continue;
            }
            else return i;
        }
        return -1;
    }
}

 

2차 풀이(결과 : 성공)

class Solution {
    public int solution(int num) {
        int answer = 0;
        long number = (long)num;
        while(number!=1){
            if(number%2==0){
                number /= 2;
                answer++;
                if(answer>=500){
                    answer = -1;
                    break;
                }
                continue;
            }
            number = number*3+1; //오버플로우 가능성?
            answer++;
            if(answer>=500){
                answer = -1;
                break;
            }
            continue;
        }
        return answer;
    }
}

 

모범 답안

class Collatz {
    public int collatz(int num) {
    long n = (long)num; //오버플로우 방지 위한 업캐스팅
    for(int i=0; i<500; i++){ //i 조건 검사가 우선 : 500번까지 시도 후
        if(n==1) return i; //(반복) n값이 1인가?
      n = (n%2==0) ? n/2 : n*3+1; //삼항식 사용 (반복) n값이 짝수이면 /2, 홀수이면 *3+1
    }
        return -1; //여기까지 왔다는 건, 500번 안에 안 끝났다는 의미.
    }

 

실패 요인

1. 오버플로우를 고려하지 못했다. 

 

인사이트

이쯤 되면 정수를 다루는 문제는 일단 long으로 바꿔놓고 시작해야겠다.