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

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

 

package com.codeup;
 
public class CodeUp100 {
 
    public static void main(String[] args) {        
        
        int num = 626331;
        int count = 0;
        
        do{
            if(num % 2 == 0) {
                num /= 2;
            }else{
                num = num * 3 + 1;
            }
            count++;
            if(count == 500) {
                break;
            }
        }while(num != 1);
        
        System.out.println(count);
    }
}

 

** 테스트3의 626331이 -1이 아닌 488이 나온다.

long타입으로 변경해보니 데이터 오버플로우가 되는 것을 확인 할 수 있다.

 

package com.codeup;
 
public class CodeUp100 {
 
    public static void main(String[] args) {        
        
        int num2 = 626331;
        int count = 0;
        
        long num = num2;
        
        do{
            if(num % 2 == 0) {
                num /= 2;
            }else{
                num = num * 3 + 1;
            }
            count++;
            if(count == 500) {
                break;
            }
            if(num >= 2147483647 || num <= -2147483648) {
                System.out.println(num);
            }
        }while(num != 1);
        
        System.out.println(count);
    }
}

int의 범위 이상의 값들이 출력되는 것을 확인 할 수 있다.

 

1. do while문을 통한 방법

class Solution {
    public int solution(int num) {
        
        int answer = 0;
        // int 오버플로우 방지를 위하여 long으로 형변환
        long temp = num;
        // 1일 때 0 반환
        if(num == 1) return 0;
        
        do{
            // 짝수일 때 2로 나누기
            if(temp % 2 == 0) {
                temp /= 2;
            // 홀수일 때 3 곱하고 1 더하기
            }else if(temp % 2 != 0) {
                temp = (temp * 3) + 1;
            }
            // count 증가
            answer++;
            // 500번 이상 시 -1 반환
            if(answer == 500) {
                answer = -1;
                // 함수 나가기
                break;
            }
        // 숫자가 1이 될 때 까지 반복
        }while(temp != 1);
 
        return answer;
    }
}

2. for문과 3항연산자를 이용한 방법

class Solution {
    public int solution(int num) {
        int answer = 0;
        // int 오버플로우 방지를 위한 long타입 형변환
        long n = num;
        // 500번만 실행
        for(int i=0; i<500; i++){
            // 들어온 숫자가 1이면 return 0;
            // 반복하여 1이 됐으면 return 반복한숫자;
            if(n==1) return i;
            // 짝수면 좌항, 홀수면 
            n = (n%2==0) ? n/2 : n*3+1; 
        }
        // for문이 끝났다는 것은 500번 반복됐다는 것이므로
        return -1;
    }
}

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges