프로그래머스 알고리즘 문제[콜라츠 추측]

# 문제

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

 

 

# 입출력 예

ex) n = 6, return = 8

ex) n = 16, return = 4    (16 → 8 → 4 → 2 → 1 이 되어 총 4번 만에 1이 된다.)

ex) n = 626331, return = -1   (626331은 500번을 시도해도 1이 되지 못하므로 -1을 리턴해야 한다)

 

 

 

# 풀이

class Solution {
 
    fun solution(num : Int): Int {
        var a = num
        var answer  = 0


        while(true){

            if(a == 1){
                break
                
            }else if(answer >= 500){
                answer = -1
                break
                
            }else{

                if (a%2 == 0){
                    a /= 2
                    
                }else{
                    var value = a.toDouble()
                    value = (value * 3) + 1
                    a = value.toInt()
                }
                
                answer ++
                
            }

        }

        return answer
    }
}

 

while(true)를 사용해서 무한반복을 실행시켜준다

입력한 숫자가 1이면 반복문을 탈출하고 answer값을 리턴해준다. answer의 초기값은 0이기 때문에 0이 리턴된다

answer >= 500 이라면 answer에 -1을 넣어서 반복문을 탈출하고 answer값을 리턴 (-1리턴됨)

그리고 입력한수가 짝수면 2를 나눠주고 answer에 1을 누적시켜준다

홀수면 3곱하고 1을 더해준뒤 answer에 1을 누적시켜준다. 이런식으로 계속 반복문을 돌다가 a값이 1이 되면 반복문 탈출하고 누적한 answer값을 리턴시켜준다. 

 

num이 6이라고 가정하면 짝수니깐 3이되고 answer에 1이 누적된다

3은 홀수니깐 계산해주면 10이되고 answer은 1이 또 누적되서 2가 될것이다

이렇게 반복문을 계속 돌다가 num이 2가되면 2로 나눠주니깐 1이 될것이고 answer은 8이 된다

이제 num이 1이니깐 반복문을 탈출하고 누적했던 answer값인 8을 반환해준다!

 

 

# 트러블 슈팅

원래 홀수일때 a = a * 3 +1 값을 계산하도록 썼었는데 이렇게했더니 몇개의 값에서 오류가 발생했다

만약에 입력값이 626331이라고 했을때 626331*3 만해도 이미 Int의 범위를 벗어난 값이 되버려서 오류가 발생하는 것이였다. 즉, 입력값이 큰값이면 Int값의 범위를 벗어나서 오류가 발생한다

따라서 이부분을 Double형으로 바꿔서 먼저 계산을 해주고 다시 Int값으로 되돌려줘서 오류를 해결했다

 

 

 

 

# 다른사람의 풀이

class Solution {
    fun solution(num: Int): Int = collatzAlgorithm(num.toLong(),0)

    tailrec fun collatzAlgorithm(n:Long, c:Int):Int =
        when{
            c > 500 -> -1
            n == 1L -> c
            else -> collatzAlgorithm(if( n%2 == 0L ) n/2 else (n*3)+1, c+1)
        }
}

 

-> while문 안에 여러 if문을 사용해서 코드를 짜면 가독성이 떨어지는데

tailrec 키워드를 사용하면 가독성과 성능을 향상시킬 수 있는 장점이 있다고한다

tailrec 키워드가 붙은 함수는 함수의 마지막 작업이 자기자신을 호출해야하는 형태여야한다!!

 

class Solution {
    fun solution(num: Int): Int {
        return processor(num.toLong(), 0)
    }

    private fun processor(n: Long, c: Int): Int {
        if (n == 1.toLong()) {
            return c
        } else if (c == 500) {
            return -1
        }
        return processor(if (n % 2.toLong() == 0.toLong()) n / 2 else n * 3 + 1, c + 1)
    }
}