[Kotlin/프로그래머스] 콜라츠 추측

요즘 코틀린의 문법에 빠르게 익숙해지기 위해 프로그래머스 Level 1 부터 문제를 풀어보고 있다.

 

알고리즘 풀다가 자주 마주하는 Int 오버플로우 문제가 나와서 실수하지 않기 위해서 글을 작성한다.

 

 

문제 소개

 

정수가 하나 주어지면 아래와 같은 과정을 거쳐서 1이되는데 몇번이나 그 과정을 거쳐야하는지 반환하는 문제이다.

( 자세한 문제 내용은 아래 링크에서 확인 )

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

https://programmers.co.kr/learn/courses/30/lessons/12943

코딩테스트 연습 - 콜라츠 추측

 

시키는대로만 하면 답이 나와야할 것 같은데, Int 로 하면 626331가 입력으로 주어지면 틀린다.  이유는 중간에 Int 범위를 벗어나기 때문이다.  아래는 "시도횟수 -> 현재 수"

.

.

.

102 -> 2139935758
103 -> 1069967879
104 -> -1085063658
105 -> -542531829
106 -> -1627595486
107 -> -813797743
108 -> 1853574068
109 -> 926787034

.

.

.

 

Int 의 범위는 다음과 같다.

-2^31 ~ 2^31 

-2147483648 ~ 2147483647 

1069967879 에서 3 곱하니 이미 Int 의 범위를 벗어난 것이다.

 

그러므로 아래 코드와 같이 Long 으로 바꿔준다.

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

    tailrec fun collatzGuess(cnt: Int, cur: Long): Int =
        if (cnt > 500) -1
        else if (cur == 1L) cnt
        else if (cur % 2 == 0L)  collatzGuess(cnt + 1, cur/2)
        else collatzGuess(cnt + 1, cur * 3 + 1)
        
}