코딩 테스트 연습 - 콜라츠 추측(프로그래머스 레벨1)

versatile309·2020년 4월 25일
0

CodingTest

목록 보기
13/19

01. 이해

정수를 입력 받아 콜라츠 추측이 성립될 때까지 몇번의 연산이 필요한지를 반환
만약 500번안에 성립되지 않으면 -1을 반환
   

02. 계획

1이 될때까지 짝수면 나누기 2, 홀수면 *3+1을 반복해서 연산 횟수를 반환한다.
도중에 연산 횟수가 500이 되면 -1을 반환한다.

03. 실행

fun solution(num: Int): Int {
    var currentNum = num.toLong()
    var count = 0
    while (currentNum != 1.toLong()){

        count += 1

        if (currentNum%2 ==0.toLong()){
            currentNum /= 2
        }else {
            currentNum = (currentNum*3) + 1
        }


        if (count == 500)
            return -1


    }

    return count
}
//재귀로 풀어보기
fun solution2(num: Int): Int {

    return getAnswer(num.toLong(),0)
}

fun getAnswer(n : Long, c: Int): Int {

    if (n == 1.toLong())
        return c
    
    if(c == 500)
        return -1

    return getAnswer(if (n%2 == 0.toLong()) n/2 else n*3+1, c+1)
}

04. 회고

처음에 while 을 사용해서 풀었는데 3번 테스트 케이스가 488번만에 끝나서 당황했다.
알고보니 정수 범위를 넘어서서 오류가 발생했던 것. Long으로 연산하니 해결 되었다.
다 풀고 나서 생각해보니 재귀로도 풀 수 있을 것 같아 시도해 봤는데 훨씬 코드가 간단해졌다.
탈출 조건이 있고 그 조건을 만족하지 않을 경우 같은 연산을 반복하는 문제니까 전형적인
재귀의 형태인 듯.

0개의 댓글