프로그래머스 | 콜라츠 추측

 

 

실패 풀이

class Solution {
    fun solution(num: Int): Int {
        var answer = 0
        var number = num
        while(true)(
        if ( num == 1){
            break
        }
        
        else if ( number == 1) {
            break
        }
        else if ( answer == 500) {
            answer = -1
            break
        }
        else if (number%2==0) {
            number /=2
            answer += 1
        } else if (number%2 != 0) {
            number = number*3 + 1
            answer += 1
        }
        )
        return answer
    }
}

테스트에서 626331 인 경우만 실패한다.

출력한걸 확인해보면

값이 1이 될 때 반복횟수가 488이다.

그래서 488을 반환한 것 같은데 왜 이렇게 된걸까?

출력을 확인해보니

중간에 음수가 되는 순간이 있었다.

다른 사람들의 질문을 참조해보니 오버플로우를 고민해보라는 글이 있다.

Int 의 최대치는 2,147,483,647

숫자의 범위가 최대치를 초과하면 오버플로우로 음수가 된다고 한다.

컴퓨터가 사용하는 이진법내용인데 컴퓨터구조 공부하면서 이진법을 분명 배웠건만 어렵게 느껴진다.

 

그래서 결국 반환타입과 숫자들을 Long 으로 변환해줬고 그 결과 정상적인 결괏값이 나왔다.

class Solution {
    fun solution(num: Int): Long {
        var answer = 0L
        var number = num.toLong()
        while(true)(
        if ( num == 1){
            answer = 0
            break
        }
        
        else if ( number == 1L) {
            break
        }
        else if ( answer == 500L) {
            answer = -1
            break
        }
        else if (number%2==0L) {
            number /=2
            answer += 1
        } else if (number%2 != 0L) {
            number = number*3 + 1
            answer += 1
        }
        )
        return answer
    }
}

 

 

 

 

다른 사람 풀이

 

짝수인 경우, 홀수인 경우를 따로 메소드로 빼서 활용하는 경우가 많았다.

 

아래는 꼬리재귀라는 tailrec 을 활용한 풀이이다.

이 부분이 뭔가 보기 전에 재귀함수를 먼저 공부해봐야 할 것 같다.🤔

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)
        }
}