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

문제

1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될 때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다.
1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다.

나의 풀이

class Solution {
    fun solution(num: Int): Int {
        var answer = 0
        var temp = num
        
        if (num != 1) {
            for (i in 0..500) {
                if (temp == 1) {
                    answer = i
                    break
                } else if (answer == 500) {
                    answer = -1
                    break
                } else {
                    answer++
                    if (temp % 2 == 0) {
                        temp /= 2
                    } else {
                        var tempDouble = temp.toDouble()
                        tempDouble = tempDouble * 3 + 1
                        temp = tempDouble.toInt()
                    }
                }
            }
        }    
        return answer
    }
}

고수의 풀이

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

---

배운점

• 1차원적인 접근으로 각 단계에 대해 반복문과 if문으로 풀어내려고 했다. 그 과정에서 int형 범위 이상의 값이 들어오는 경우에는 잠시 데이터 형태를 double로 바꾸어서 처리하는 게 필요했는데, 이 부분을 인지하고 바꾸는 데에 시간이 오래 걸렸다.
• 고수의 풀이를 보면 접근법 자체가 다르다.
  • 별도의 함수를 하나 더 만들어서 풀었다(처음에 문제를 보고 재귀 함수가 생각나서 함수를 하나 더 만들까 고민하다가 집어지웠는데, 고수는 그걸 실현해냈다.)
  • tailrec fun은 처음 봤다.
    • 꼬리재귀(tail recursive). 함수의 마지막 부분에 자기 자신을 호출하는 재위 형태이다. tailrec이라는 키워드는 재귀 함수가 스택 오버플로우 없이 최적화 될 수 있도록 도와준다. 즉, 컴파일러가 재귀 함수를 반복문 형태로 최적화하게 된다.
    • 다만 이 최적화는 재귀 호출이 함수의 마지막 부분에서만 일어날 때 가능하다.
  • when문도 실제로 사용되는 것을 본 것은 처음이다.
    • when문은 switch문을 대체로 사용되는 표현식이다.
      • c > 500 : c가 500보다 크면 -1 반환
      • n == 1L -> c : n이 1이면 c 값을 반환
        • 콜라츠 추측이 성공적으로 1에 도달했을 때의 결과 값
      • else : 함수를 재귀적으로 호출
        • 짝수이면 n/2, 홀수이면 n*3+1로 계산
  • 여기서 애초에 n을 Long 타입으로 받아와서 int 범위 이상의 숫자가 왔을 때에도 오류가 나지 않도록 하는 것까지 챙기면 완벽한듯하다.

---

[TIL-240226]