[Kotlin] 콜라츠 추측 (프로그래머스 알고리즘)

 

문제

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

 

 

---

 

접근

 

• while문안에 if를 분기시켜 500번까지 반복시키고, 500번 안에서 return 값 출력, 밖에서 -1 출력
• 처음 구상한 방식은 별 다른 고민 없이 아래와 같은 방식이었다.

// 구상 (결과값 다름)

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

• 아무 생각 없이 코드를 짜다보니 var num = num으로 선언해 버렸다.
  나중에 코드짤 때 문제가 없기 위해선 var n = num 으로 설정하고 모두 n으로 바꿔주는 게 맞다.
• repeat < 500 으로 부등호를 설정해야 500번까지 반복한다. '<=' 는 잘못되었다.
• 그런데 아무리 위와 같이 수정을 해줘도 n이 626331인 경우에 결과값이 -1이 아닌 488이 나왔다.
• (num * 3) + 1 부분에서 Int의 범위를 초과하기 때문이다.
• 대강 Long으로 변수 n의 자료형을 수정해 주었다.

 

---

 

성공 코드

 

class Solution {
    fun solution(num: Int): Int {
        
        var repeat = 0
        var n = num.toLong()
        
        while(repeat < 500){
        if(n == 1L){
            break
             }
        else if(n % 2 == 0L) {
             n = n / 2
        }else{
             n = n * 3 + 1
             }    
        repeat++
        }
        
        if (repeat < 500) return repeat else return -1
        
    }
}

 

 

---

 

설명

 

1. 500까지 반복이 되는지 확인하기 위해 repeat 변수를 선언하고, repeat < 500 동안 반복되는 while문을 만든다.
2. n이 저장하는 값은 상황에 따라 Int의 범위를 넘어갈 수 있으므로 .toLong()으로 형변환 시켜준다.
3. while문 안에서 n == 1인 경우 break, n이 1이 아닌 경우 짝수/홀수에 맞추어 식을 작성한 뒤 repeat를 1씩 올려준다.
4. 조건에 따라 무한 반복하다가 n이 1이 되거나, repeat가 500이 되면 밖으로 나온다.
5. repeat(반복값)이 500보다 작은 경우 repeat를 결과값으로 반환하고, 더 큰 경우 -1을 반환한다.

 

---

 

다른 방법

 

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

• tailrec이라는 꼬리재귀함수를 이용한 풀이다.
• 콜라츠 추측을 구현한 함수인 solution과 이를 재귀적으로 호출하는 collatzAlgorithm 함수로 구성
• solution 함수
  - solution 함수는 주어진 num을 Int로 받아서 collatzAlgorithm 함수에 전달
  - 반환 값은 collatzAlgorithm 함수의 반환 값
• collatzAlgorithm 함수
  - collatzAlgorithm 함수는 콜라츠 추측 알고리즘을 재귀적으로 구현
  - n과 c 두 개의 매개변수를 가지며, n은 현재 수이고 c는 이전까지의 반복 횟수를 나타냄
• when 표현식을 사용하여 세 가지 경우를 처리
  (1) c > 500일 때: 반복 횟수가 500을 초과하면 -1을 반환
  (2) n == 1L일 때: 현재 수가 1이면 현재까지의 반복 횟수인 c를 반환
  (3) 그 외의 경우: 현재 수가 짝수인지 홀수인지에 따라 다음 수를 결정하고, 이전 반복 횟수 c에 1을 더하여 재귀적으로 다시 collatzAlgorithm을 수행하여 다음 수를 계산
• 함수는 tail-recursive로 구현되어 있으며, 재귀 호출이 함수의 마지막 연산으로 수행됨.
  이를 통해 메모리를 절약할 수 있음