콜라츠 추측

https://school.programmers.co.kr/learn/courses/30/lessons/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을 완성해 주세요. 단, 작업을 500번을 반복해도 1이 되지 않는다면 –1을 반환해 주세요.

 

제한 사항

• 입력된 수, num은 1 이상 8000000 미만인 정수입니다.

입출력 예

 

n	result
6	8
16	4
626331	-1

 

입출력 예 설명

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

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

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

---

이번 문제는 어려웠던건 아니다...근데 이문제를 통해서 모르는것을 많이 알아서 적어본다....

 

우선 나는 이렇게 풀었다

static public int solution(int num) {
        int count = 0;
        long result = num;
        while (result != 1) {

            if (result % 2 == 0) {
                result = result / 2;
                count++;
            } else if (result % 2 != 0) {
                result = result * 3 + 1;
                count++;
            }

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

여기서 num으로 계산을 바로했는데 중간에 오버플로우가 발생을 해서 result 변수를 long타입으로 생성하고 num 값을 그대로 넣어서 진행했다... 여기까지는 괜찮았다. 쉬운 문제이다..

 

그렇게 지나갔다가 같이 공부하는 팀원분이 오버플로우때문에 진행을 못하고있다고 도움을 요청하셔서 long타입 힌트만 주었는데 갑자기 다른분이 자기는 long 타입 변환 안했는데 문제 통과했어요!!!!!!!!!!!!!!!!!!!!!!!!! 여기서 모두들 놀랐다... 뭐지? 뭐야?

 

이상하다 나는 분명히 int 로 했을때 3번째 입출력 예제를 실행하면 기대값이 안나오고 엉뚱한 값이 나오는데... 뭐지?!

 

바로 그문제의 코드이다.

static public int solution2(int num) {
        int count = 0;
        while (num != 1) {

            if (num % 2 == 0) {
                num = num / 2;
            } else if (num % 2 == 1) {
                num = num * 3 + 1;
            }
			count++;
            if (count > 500) return -1;
        }
        
        return count;
    }

그래서 다같이 이 코드를 분석을 해보았다...

지금 이코드에 입출력 예제3번을 실행했다 그러면 num값이 언젠가는 오버플로우가 발생한다.. 그러면서 음수값으로 넘어가면서 문제가 발생한다. 음수로 넘어가고 2로 나누었을때 나머지가 -1이 나오므로 조건문을 타지않는것이다... 하지만 count를 조건문 밖에다가 작성해서 코드는 정상적으로 돌아간다.. 이게 맞는건지는 모르겠지만 일단 해결하셨다...ㄷㄷ

 

무튼 그건 그거고 우리는 result(num) 값을 하나하나 찍어보았다.. 104번째 계산에서 int범위를 초과해서 음수로 변했다..

?! 왜 갑자기 음수로 변하지? 여기서 의문이 생긴것이다.. int범위를 초과하면 초과 범위만큼 int의 음수 범위에서 다시 시작했었다... 이렇게 새로운걸 배웠다..

 

이게 보수 컴퓨터의 보수표현??? 이것떄문에 범위를 초과하면 음수부터 시작한다 음수도 마찬가지로 초과를하면 양수부터 시작한다... 머리로는 이해를 했지만 설명하기는 조금 부족한거 같다.... 이거는 나중에 지식방에 보수를 따로 정리하도록 하겠다...

 

무튼 정말 좋은걸 배운것 같다.