[프로그래머스]콜라츠 추측 - Kotlin / 꼬리 재귀에 관해

1.문제

1-1 문제 이해

 

1. 주어진 값 짝수 -> 나누기 2

2. 주어진 수 홀수 -> 곱하기3 더하기1

3. 위 과정을 주어진 수가 1이 될 때 까지 반복

 

각 주어진 수에 따라 몇번 반복했는지 

반복 횟수를 구하는 문제

 

단, 500번이 넘어가면 -1 리턴

 

1-2 풀이 과정

1. 1이 될 때 까지

 

특정 조건까지 계속 반복해야 하기에 while을 이용했다.

class Solution {
    fun solution(num: Int): Int {
        var input = num
        while(input != 1){ // 1이 될때까지
            
        }
    }
}

2. 짝수면 나누기 2 / 홀수면 곱하기3 더하기1

while속에 if문을 통해 

주어진 수를 2로 나눈 나머지가 0인게 맞으면 짝수이므로 

주어진 수 나누기 2

 

아니라면

주어진 수 곱하기3 더하기 1 조건을 주었다.

class Solution {
    fun solution(num: Int): Int {
        var input = num
        
        while(input != 1){
            if(input % 2 == 0){     	//주어진 수를 2로 나눈 나머지가 0인게 맞으면 짝수
                input /= 2          	// 주어진 수 나누기 2
            }else{ 						// 아니라면
                input = input *3 +1     // 주어진 수 곱하기3 더하기 1
            }
        }
    }
}

3. 반복 횟수 카운트

각 작업 총 횟수를 구하기 위해 if문 속에

한 작업을 할때마다 answer 변수의 값을 1씩 증가 시켰다.

class Solution {
    fun solution(num: Int): Int {
        var answer = 0 				// 초기화
        var input = num
        
        while(input != 1){
            if(input % 2 == 0){
                input /= 2
                answer += 1			// 작업당 1씩 증가
            }else{
                input = input *3 +1
                answer+= 1			// 작업당 1씩 증가
            }       
        }
        return answer				
    }
}

 

4. 반복 횟수 500회 넘어갈 시 -1 리턴

만약 작업 횟수가 500회가 넘으면 

-1 리턴 

 

break로 빠져나오기

class Solution {
    fun solution(num: Int): Int {
        var answer = 0
        var input = num
        
        while(input != 1){
            if(input % 2 == 0){
                input /= 2
                answer += 1
            }else{
                input = input *3 +1
                answer+= 1
            }
            if(answer > 500){ // 작업 횟수가 500회가 넘으면
                answer = -1   // -1 리턴
                break         // while문 빠져나오기
            }
        }
        return answer
    }
}

 

 

엇.. 마지막 부분의 문제점을 발견했다.

 

정말 여러가지 생각해봤는데 

 

혹시 자료형의 문제는 아닐까라고 생각하여

 

int를 Long으로 바꾸어 보았다.

class Solution {
    fun solution(num: Int): Int {
        var answer = 0
        var input:Long = num.toLong() 	 // Long으로 형변환
        
        while(input != 1.toLong()){ 	 // Long으로 형변환
            if(input % 2 == 0.toLong()){ // Long으로 형변환
                input /= 2
                answer += 1
            }else{
                input = input *3 +1
                answer+= 1
            }
            
            if(answer == 500){
                answer = -1
                break
            }
            
            
        }
        return answer
    }
}

 

 

 

 

오 맞았다!

 

2. 다른 문제 풀이

 

2-1 tailrec(꼬리재귀)

 

# when을 품은 재귀 함수 생성

	tailrec fun collatzAlgorithm(n:Long, c:Int):Int = // 매개변수로 주어질 수, 카운트
        when{										  
            c > 500 -> -1						// 카운트가 500을 넘기면 -1 리턴
            n == 1L -> c						// 주어진 수가 1이 되면 카운트 리턴
            else -> collatzAlgorithm(if( n%2 == 0L ) n/2 else (n*3)+1, c+1)
            // 두 조건 중 하나 될 때까지 스스로 계속 루프(문제의 조건)
        }

 

 

# 최종 답변

 

class Solution {
    fun solution(num: Int): Int = collatzAlgorithm(num.toLong(),0)
    							// num 받아오기, 카운트 시작
  	tailrec fun collatzAlgorithm(n:Long, c:Int):Int = // 매개변수로 주어질 수, 카운트
        when{										  
            c > 500 -> -1						// 카운트가 500을 넘기면 -1 리턴
            n == 1L -> c						// 주어진 수가 1이 되면 카운트 리턴
            else -> collatzAlgorithm(if( n%2 == 0L ) n/2 else (n*3)+1, c+1)
            // 두 조건 중 하나 될 때까지 스스로 계속 루프(문제의 조건)
        }
}

 

tailrec은 꼬리재귀(tail recursive)라는 의미

추가적인 연산 없이

자신 스스로 재귀적으로 호출하다가

어떤 값을 리턴하는 함수

 

특정 조건 충족될 때까지

반복적 로직 처리해야 하는 상황에 쓰일 수 있음

 

 

사실 이럴 때

while문을 사용하는 것이 일반적 + 성능상의 이점 제공

 

하지만

 

코드의 가독성 저하 가능성 있음

 

반면

재귀 함수 사용 시  코드 가독성 개선

But

성능 문제, 스택 오버플로우 위험