2024-05-22 오늘의 TIL

콜라츠 추측

1937년 독일의 수학자 롤프 콜라츠(Rolf Collatz)에 의해 제안된 수학적 문제로, 아직까지 해결되지 않은 수학의 난제 중 하나입니다. 이 추측은 다음과 같은 간단한 규칙을 따르는 수열을 다룹니다:

어떤 양의 정수 n \에서 시작합니다.
n이 짝수라면 n을 2로 나눕니다.
n이 홀수라면 n에 3을 곱하고 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을 반환해 주세요.

풀이

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

결과

왜 answer ++인데 -값이 나왔을까....
그래서 다른 방법으로 수정을 해보았다.

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

회고

분명 잘 작성했다고 생각했는데 저런 수가 튀어나와서 당황하였다.
오히려 간단하게 줄이니까 통과가 되었는데..
왜 저런 수가 튀어나왔나하면 조건문을 빠져나가지 못하고 오버플로우가 났다고 하는데
or 조건문을 잘 만들었다고 생각했는데 왜 무한루프로 빠졌을까...

해결법

고민을 해본결과 아차 싶었다 or문은 둘중에 하나가 맞으면 true를 내보내는데 whlie은 true가 나오면 반복하기 때문에 테스트 1,2 경우에는 둘다 500번 반복전이라 둘다 false 상태여서 종료 되었고 3번째는 1이될때 까지 반복하다가 500이 넘으면 true가 되어서 무한반복을 하게되어서 오버플로우가 발생하였다.