(알고리즘) 콜라츠 추측 문제 풀이

알고리즘 문제 중에 쉬운 듯 생각을 잘 해야 하는 콜라츠 추측 문제를 한번 풀어봤다

 

 

문제의 요약은 대충 이렇다

 - 주어진 값이 짝수 일 경우 2를 나눈다

 - 주어진 값이 홀수 일 경우 3을 곱한 후에 1을 더한다

 - 연산 값이 1아 될 때 까지 계속 위 작업을 반복한다 

 - 1인 경우에는 0을 반환한다

 - 500번 이상 반복할 경우에는 -1을 반환한다

 

문제의 해결 과제를 이런식으로 나누어서 생각했다

 1. 주어진 값이 짝수와 홀수를 검사 후 연산 기능

 2. 연산 값이 1이 될 때 까지 계속 위 작업을 반복하는 기능

 3. 최초 입력 값이 1인 경우와 500번 이상 반복한 경우에 예외 처리

 

 1. 연산 횟수와 연산 값을 임시로 저장하는 변수 생성

 2. 주어진 값이 짝수와 홀수를 검사 후 연산 기능

짝수와 홀수 같은 경우는 %(나머지 연산자) 를 활용하였다 만약에 2를 나머지 연산을 할경우 0이 나올 경우 짝수 이외의 값이 나올 경우 홀수로 짝수 홀수를 구분하였다

fun solution(num: Int): Int {
   var answer = 0
   var tempNumber = num
 
   if(tempNumber % 2 == 0L){
     tempNumber /= 2    
   }else{
     tempNumber = (tempNumber * 3) + 1
   }
   
   return answer
}

 3. 위 작업을 1이 될때 까지 반복한다

위에서 연산한 결과를 1이 될 때 까지 반복을 한다 따라서 while을 사용하여 1이 아닐때만 반복하게끔 구성을 해주었다

fun solution(num: Int): Int {
    var answer = 0
    var tempNumber = num

    while (tempNumber != 1){
        if(tempNumber % 2 == 0){
            tempNumber /= 2
        }else{
            tempNumber = (tempNumber * 3) + 1
        }
        
        //반복할 때 마다 연산 횟수 증가
        answer += 1
    }
    return answer
}

 4. 최초 입력 값이 1인 경우와 500번 이상 반복한 경우에 예외 처리를 한다

처음 입력 받았을 때 값이 1이면 바로 함수를 리턴하며 반복 횟수가 500번이 넘었을 경우 answer에 -1을 넣고 리턴한다

   fun solution(num: Int): Int {
    var answer = 0
    var tempNumber = num
    if(tempNumber == 1) {
        return answer
    }

    while (tempNumber != 1){
        if(tempNumber % 2 == 0){
            tempNumber /= 2
        }else{
            tempNumber = (tempNumber * 3) + 1
        }
        answer += 1
        if(answer >= 500){
            answer = -1
            break
        }
    }
    return answer
}

이런 식으로 코드를 짜고 코드를 돌려봤는데...

 

626331이라는 값을 넣었을 경우에 500이 넘기 때문에 예상 값이 -1 이어야 하는데 488이 나오는 것 아닌가;;

그래서 해당 부분을 확인하기 위해서 위에서 연산한 다음에 연산 결과를 출력하는 코드를 작성해서 출력해봤다

 

그런데..

중간에 음수가 나오는 것 아닌가;; 이게 무슨 일인가 하고 찾아봤는데

 

코틀린의 Int형은 4바이트(32비트) 이고 -2,147,483,648 ~ 2,147,483,647 까지 표현이 가능한데 이 값을 넘어버리면 제일 마지막에 있는 부호를 구분하는 비트를 넘어가기 때문에 의도치 않게 음수로 바뀌는 것이 었다 ( + 음수로 바뀌면서 값도 바뀌는 기적...)

 

따라서 이 문제는 연산 값을 Long 타입으로 바꿔서 연산을 하면 정상적으로 출력이 될 것 같아서 

   fun solution(num: Int): Int {
    var answer = 0
    var tempNumber:Long = num.toLong()
    if(tempNumber == 1L) {
        return answer
    }

    while (tempNumber != 1L){
        if(tempNumber % 2 == 0L){
            tempNumber /= 2
        }else{
            tempNumber = (tempNumber * 3) + 1
        }
        answer += 1
        if(answer >= 500){
            answer = -1
            break
        }
    }
    return answer
}

전부 Long 타입으로 바꾸고 출력해보니까 정상적으로 작동하는 것이 확인되었다

 

- 오늘의 결론

- 커보이는 값이 보이고 이 값을 곱하기등의 큰 연산을 반복적으로 수행할 경우에는 Long 타입을 쓰는 것이 낫다

- 물론 로직 따라 다르겠지만 ㅎㅎ