[Java] 정수 오버플로우로 인한 반환값 다름정리 - (프로그래머스 12943 콜라츠 추측)

프로그래머스 12943. 콜라츠 추측 문제를 풀다가 입력값의 타입을 int 에서 long으로 변환한 것 하나로 반환값이 다르게 나오는 것을 확인 할 수 있었다. 그 이유에 대해서 알아보고 정리해보고자 한다.

 

---

 

먼저 문제는 프로그래머스 12943. 콜라츠 추측이다.

 

문제 설명

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 미만인 정수입니다.

 

입출력 예

입출력 예 #1
문제의 설명과 같습니다.

 

입출력 예 #2
16 → 8 → 4 → 2 → 1 이 되어 총 4번 만에 1이 됩니다.

 

입출력 예 #3
626331은 500번을 시도해도 1이 되지 못하므로 -1을 리턴해야 합니다.

 

 

 

---

 

처음 내가 쓴 문제의 답

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

            if(count>=500){
                return -1;
            }
        }
        return count;
    }
}

처음에는 이렇게 코드를 작성하고 코드 실행을 돌렸다. 그랬더니,

결과가 다음과 같이 나왔다. 

테스트 1과 2는 성공했지만 3은 결과값이 기대값과 다르게 나온 것이다.

 

그래서 이러한 문제나 나타난 이유를 생각해보고 알아 보았다.

 

 

원인

내가 알아본 바로는 Collatz 추측의 작업 중에는 숫자가 매우 커질 수 있고, 정수 오버플로우로 인해 예상치 못한 동작이 발생할 수 있는데 이게 원인이 된 것 같았다.

 

위에서 주어진 코드를 실행했을 때, 테스트 3의 입력값 `num`이 626331라면 Collatz 추측에 의해 계산된 중간 결과가 매우 커질 수 있다는 것이다. 

예를들어, 작업 중에 숫자가 3131656이 되었다고 가정을 한다면 이 값은 처음에 선언했던 num의 `int` 데이터 형식의 범위를 초과하게 된다. 따라서 이로 인해 정수 오버플로우가 발생하는 것이다.

 

한마디로, 주어진 입력값과 중간 결과값이 int 형식으로 표현할 수 있는 최대값을 넘어가게 되면서 오류가 발생한 결과라고 할 수 있다.

 

정수 오버플로우(Overflow)란?
- 컴퓨터에서 사용하는 정수 데이터 타입이 표현할 수 있는 범위를 벗어나는 경우 발생하는 현상이다.
- 컴퓨터 메모리에 저장된 값이 정해진 비투 수를 초과하게 되면 해당 값은 부호 없이 또는 부호와 함께 오버플로우가 발생한다.
- 오버플로우가 발생하면 값은 데이터 타입의 최소값으로 랩어라운드 된다. 이는 예기치 않은 결과를 초래하여 프로그램의 안정성과 실뢰성을 위협할 수 있다.

 

 

해결방법

그렇다면 이것을 어떻게 해결하면 되냐면,

int 보다 더 큰 수를 다룰 수 있는 데이터 타입으로 변환시키면 된다.

 

따라서 내가 사용한 방식은 `long` 타입으로 변환이다.

 

수정한 코드

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

            if(count>=500){
                return -1;
            }
        }
        return count;
    }
}

long n = (long)num; 의 코드 추가로 num을 long 타입으로 바꾸어 새로운 n 이라는 변수를 선언해주었고,

해당 코드를 실행해보았을때

테스트 1,2,3 모두 성공한 것을 볼 수 있었다.

 

 

 

---

정리

문제를 풀때도 그렇고 프로젝트를 진행했을때도 데이터가 크면 대부분 long 타입을 사용하거나 크게는 CLOB 타입까지 사용했었다. 그때는 처음부터 큰 수를 다룰 수 있는 타입을 바로 사용했기 때문에 정수 오버플로우라는 개념에 대해 크게 생각하지 않았었는데 문제를 풀면서 이런 문제가 발생할 수 있구나라는 것을 알게 되었다.

지금 풀고 있는 문제는 작은 문제풀이이기 때문에 크게 와닿지 않지만 개발을 하기 위한 코드 작성에서는 조그마한 에러가 생기면 바로 결과값이 바뀌어 큰 나비효과를 불러 올 수 있을 것 같다.

따라서, 앞으로는 코드를 작성할 때 데이터 타입에 조금 더 신경을 써서 오버플로우가 발생하지 않도록 주의해야겠다.