[JAVA/프로그래머스] 콜라츠 추측 풀이

썸네일

 

 

 

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

<입출력 예>

n	result
6	8
16	4
626331	-1

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

[최초 풀이]

처음 풀이는 다음과 같다.

class Solution {
    public int solution(int num) {
        int cnt = 0;
        while(num>1){
            if(cnt>500) break;
            if(num%2==0) num /= 2;
            else if(num%2==1) num = (num*3)+1;
            cnt+=1;
            System.out.println("num:"+num+"/cnt:"+cnt);
        }
        cnt = cnt>500 ? -1:cnt;

        return cnt;
    }
}

그런데 다음과 같은 오류가 떴다.

 

주어진 수는 626331인데, count가 104번에서 끊기니 이상했다..

아무리봐도 코드 자체엔 문제가 없었다.

 

 

num의 연산 흐름을 보니, 쭉 잘되다가 마지막에 난데없이 -1085063658... 이라는 이상한 결과와 함께 break 됨...

break 가 될만한 경우의 수는 다음과 같았다.

 

a) cnt>500 일 때, break

b) num>1 일 때, break

=> 둘 다 해당 안됨.

 

그럼, 연산이 이상한가?

break 바로 직전 num인 1,069,967,879을 짝수/홀수인지 보니 -> 홀수에 해당.

홀수는 *3 해준 뒤 +1을 해야하므로 해당 공식대로 계산하면 3,209,903,638 라는 수가 나온다.

혹시 이게 짝수로 인식됐나? 하고 보니 그건 더더욱 아니다... 결과로 나온 값은 전혀 예측 안되는 숫자..

한참 생각하다가 보니, 이게 정수 오버플로우 형태임을 깨달았다.

 

 

(↓ 참고하기 좋은 글)

[JAVA] 자바 정수형 사용하기/int형과 long형의 정확한 차이점

 

 

---

 

 

즉, count가 104번째 되는 지점에서 오버플로우가 발생하며 값손실이 발생하여 

오버플로우로 오류가 난 것!

데이터 형태를 처음부터 long으로 지정해주니, 잘 돌아갔다.

 

최종적인 풀이는 다음과 같다.

 

 

 

<최종 풀이>

class Solution {
    public int solution(long num) {
        int cnt = 0;
        while(num>1){
            if(cnt>500) break;
            if(num%2==0) num /= 2;
            else if(num%2==1) num = (num*3)+1;
            cnt+=1;
            System.out.println("num:"+num+"/cnt:"+cnt);
        }
        cnt = cnt>500 ? -1:cnt;

        return cnt;
    }
}

 

 

이런 경우도 있구나...앞으로는 데이터 형태로 인한 오류도 염두해두어야겠다.