오늘의 코딩 테스트(Collatz 추측)

1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될 때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측이다. 작업은 다음과 같다.

 

1. 입력된 수가 짝수라면 2로 나눈다.
2. 입력된 수가 홀수라면 3을 곱하고 1을 더한다.
3. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복한다.

위 작업을 몇 번이나 반복해야 하는지 반환하는 함수, solution을 완성하라

단, 주어진 수가 1인 경우에는 0을, 작업을 500번 반복할 때까지 1이 되지 않는다면 -1을 반환

 

제한사항

입력된 수, num은 1이상 8,000,000 미만인 정수

 

class Solution {
    public int solution(int num) {
        
        if (num == 1) return 0;
        
        long n = (long)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;
    }
}

 

위의 코드를 만들때 while 문 조건을 잘못 지정했었다.

"num == 1" 이 조건을 넣었었는데 이는 num이 1일때만 실행이 되는 것이다.

내가 생각한 num이 1이 될 때까지가 아니었다.

num이 1이 될 때까지 실행하고 싶다면

while (num != 1) {

}

while (num > 1) {

}

이와 같은 조건을 넣어줘야 한다.

 

또한 if문 뒤에 홀수를 확인할 수 있는 

else if (num % 2 == 1)

를 넣었는데 이 구문은 사실 불필요하다 모든 수는 짝수 아니면 홀수이기에 짝수만 판별해주면 나머지는 홀수이기 때문이다.

 

long n = (long)num;

또한 int 형식으로 받은 num을 long으로 변환해주어야 한다는 것을 알았는데

그 이유는 계산 과정에서 오버플로우가 발생할 수 있기 때문이다.

int의 최대값은 2,147,483,647이다.

num은 8,000,000 미만이라고 하였지만 계산 과정에서 int 범위를 초과할 가능성이 있어 long 변환이 필요하다.

실제로 콜라츠 추측의 특성상 중각 계산 값이 매우 커질 수 있다.

(long)은 형변환(타입 캐스팅) 연산자인데 원래 작은 타입에서 큰 타입으로의 변환은 자동으로 이루어지지만

명시를 함으로써,

코드를 읽는 사람에게 의도적인 현변환임을 알려주고

코드의 가독성을 높이며

다른 개발자가 코드를 이해하기 쉽게 해줄 수 있다.

 

다른 방법

 

재귀 방식

public int solution(int num) {
    return collatz((long)num, 0);
}

private int collatz(long n, int count) {
    if (count >= 500) return -1;
    if (n == 1) return count;
    
    return collatz(n % 2 == 0 ? n/2 : n*3+1, count+1);
}

 

Stream API 활용

public int solution(int num) {
    if (num == 1) return 0;
    
    return IntStream.iterate(0, i -> i + 1)
        .limit(500)
        .reduce(-1, (count, i) -> {
            long n = num;
            for (int j = 0; j <= i; j++) {
                if (n == 1) return i;
                n = (n % 2 == 0) ? n/2 : n*3 + 1;
            }
            return count;
        });
}

 

최적화된 반복문

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