[프로그래머스 / Level1] 콜라츠 추측 (Java)

문제

https://programmers.co.kr/learn/courses/30/lessons/12943

코딩테스트 연습 - 콜라츠 추측

 

기존 코드 (실패)

class Solution {
    public int solution(int num) {
        int answer = 0;
        
        while(num != 1){
            if(num % 2 == 0){
                num /= 2;
            }else{
                num = (num * 3) + 1;
            }
            
            answer++;
            if(answer >= 500) { return -1; }
        }
        
        return answer;
    }
}

 

틀린 이유

연산 과정은 틀리지 않았으나, 계속 3번째 테스트케이스에서 실패가 떴다.
위 소스코드는 연산 횟수가 500번을 넘어갈 경우 -1을 반환하는데, 입력값이 626331일 경우 이 경우에 부합해 -1이 반환된다는 것. 그러나 테스트 결과, 626331은 488번째 연산에서 반복이 제대로 종료된다.

1, 2번째 테스트케이스와 3번째 테스트케이스의 눈에 띄는 차이점은 입력값이 크다는 점.
연산 과정을 살펴보기 위해 매 반복마다 num값을 출력하도록 수정한다.

class Solution {
    public int solution(int num) {
        int answer = 0;
        System.out.println(num);
        
        while(num != 1){
            if(num % 2 == 0){
                num /= 2;
            }else{
                num = (num * 3) + 1;
            }
            System.out.println(num);		//현재 num값 출력
            answer++;
            
            if(answer >= 500) { return -1; }
        }
        
        return answer;
    }
}

 

실행결과를 확인하던 중 num값이 음수로 나오는 부분을 발견했다.

위 코드에서는 num에 나눗셈/곱셈/덧셈만 수행하기 때문에 음수가 나올 수 없다.
그런데도 음수가 나왔다는 건 num이 int형의 최대값(양수)을 초과하자 오버플로우가 발생해 최소값(음수)로 돌아간 것.
오버플로우에 의해 num값이 중간에 왜곡되어 기대한 결과와 다르게 나온 것이다.

최대값 + 1 = 최소값
최소값 - 1 = 최대값

 

3번 테스트케이스와 같이 큰 값을 입력받을 경우 int타입이 표현할 수 있는 값의 범위(-2,147,483,648 ~ 2,147,483,647)를 넘어서는 오버플로우(overflow)가 발생할 수 있다.
큰 정수를 입력받을 때는 int타입보다 값의 범위가 큰 long타입 변수를 사용해야 한다.

 

개선 코드 (성공)

매개변수로 전달받은 int타입 num값을 long타입 변수에 저장해서 사용.

class Solution {
    public int solution(int num) {
        long n = num;
        int answer = 0;
        
        while(n != 1){
            if(n % 2 == 0){
                n /= 2;
            }else{
                n = (n * 3) + 1;
            }
            answer++;
            if(answer >= 500) { return -1; }
        }
        
        return answer;
    }
}