CodingTest #32 Kotlin 나머지가 1이 되는 수 찾기, 콜라츠 추측 문제풀이

출처 핀터레스트

 

하루 시작에 머리를 맑게 해 주는?

 

코딩 테스트를 풀고 정리해본다.

 

우선 

 

나머지가 1이 되는 수 찾기이다.

 

 

나머지가 1이 되는 수 찾기

 

//나머지가 1이 되는 수 찾기
class FindANumberWhoseRemainderIs1 {
    fun solution(n: Int): Int {
        var x = 1
        while(true) if(n.rem(++x) == 1) break
        return x
    }
}

문제는 입력받은 n 값을 나누어 나머지 1인 최솟값을 구하는 문제였는데,

 

원하는 값이 나올 동안 while문을 돌려 1씩 증가시켜 값을 얻었다.

 

증감 연산자를 전위형으로 하였고,

 

n을 나누어줄 때 rem 메서드를 사용하였다.

 

rem 메서드는 나머지를 구해주는 메서드이다.

 

---

 

여기서 한 가지 배운 사실이 있다.

 

숫자끼리에 연산을 해주는 연산자는 다음과 같다.

 

+, -, *, /, % 정도가 있는데,

 

코틀린 내장 함수에는 각각

 

plus(), minus(), times(), div(), rem() 메서드들로 위에 연산자를 대체할 수 있다.

 

굳이?라고 생각할 수 도 있다.

 

기존 연산자와 연산자 메서드의 차이점은 아래와 같다.

 

val x = 1
val y = 2
val z = 3

println(x + y * z)          // equivalent to 1 + (2 * 3) -> 7
println(x.plus(y).times(z)) // equivalent to (1 + 2) * 3 -> 9

 

보통 수식을 계산하게 되면 곱하기나 나누기를 먼저 계산하고 나머지 연산자를 계산한다.

 

계산식이 길어지면, 이러한 점을 혼동할 수 있기 때문에

 

이름으로 명명하는 방법도 있는 것이다.

 

이러한 표현을 연산자 오버 로딩(Operator Overloading)이라고 한다.

 

기존 자바에는 연산자 오버 로딩이 없었지만,

 

코틀린에는 제공하고 있다.

 

아래는 연산자 오버로딩 표이다.

 

 

나 같은 경우는 이 표현이 더 직관적이라 저 메서드를 사용해보았다.

 

다음 문제로 넘어가 보자.

 

콜라츠 추측

 

class CollatzGuess {

	private var cnt: Long = 0L

    fun solution(num: Int): Int {
    	if(num != 1L) runCollatz(n)
        retrun num
    }
    
    fun runCollatz(n: Long) {
        cnt++

        if(cnt == 501L) {
            cnt = -1L
            return
        }

        val result = when(n.toInt().rem(2)) {
            0 -> { //짝수라면
                n.div(2)
            }
            else -> { //홀수라면
                n.times(3).plus(1)
            }
        }

        if(result != 1L) runCollatz(result)
        else return
    }
}

 

기존에는 이런 식으로 문제를 풀었다.

 

해당 문제는 재귀 호출에 관한 문제이다.

 

원하는 값이 나올 때까지 계속해서 같은 메서드를 호출하는 문제인데,

 

이 재귀 호출에 문제점은 같은 메서드가 호출될 때마다 

 

지나지게 많은 버퍼(buffer)를 요청해서 운영체제가 더 이상 값을 할당할 수 없는

 

StackOverFlow 현상이 일어나게 된다.

 

이러한 문제점을 해결해주는 코틀린의 포함된 예약어가 있는데,

 

바로 tailrec이다.

 

문자 그대로 일명 꼬리 함수(재귀 함수)에 특화된 함수인데,

 

이 예약어를 지정하게 되면, 버퍼에 할당 값이 쌓이는 게 아니라,

 

마치 while문이나 for문 같은 반복문 형태로 메서드를 변환해주는 역할을 한다.

 

아래 코드가 tailrec을 적용한 코드 답안이다.

 

class CollatzGuess {

    fun solution(num: Int): Int = runCollatz(num.toLong(), 0)
    
    tailrec fun runCollatz(n: Long, c: Int): Int =
        when {
            n == 1L -> c
            c > 500 -> -1
            else -> runCollatz(
                if(n.toInt().rem(2) == 0)
                    n.div(2)
                else
                    n.times(3).plus(1), c.plus(1))
        }
}

 

우선 코드가 훨씬 간결해진 점이 눈의 띈다.

 

중요한 것은 이게 아니다.

 

tailrec 메서드가 원하는 값이 나올 동안 계속 호출되는 것을 볼 수 있는데,

 

그 전 코드처럼 계속 같은 메서드를 할당하는 것이 아닌,

 

runCollatz안에 마치 반복문처럼 (한 번만 할당) 내부에서만 코드가 반복되게 해 준다.

 

이러한 장점으로 재귀 호출 때 많이 써먹으면 좋을 것 같다.

 

또 한 가지 더 알아야 할 점이 있다.

 

파라미터로 전달받은 num Int값을 왜 Long으로 변환해서 쓰는지 궁금할 수 있다.

 

위에 스택오버플로우와 다르게

 

이번 문제는 정수 오버플로우(IntegerOverFlow) 문제이다.

 

정수 오버플로우는 정수의 값이 증가하면서

 

허용된 가장 큰 값보다 더 커져서 실제 저장되는 값이

 

의도치 않는 값일 수도 있게 만드는 현상이다.

 

 

문제 지문에서 626331이란 입력값을 넣어 출력을 해보았는데,

 

원래 나와야 할 -1이 안 나오고, 488이란 값이 나왔다.

 

원래 같으면 500이란 횟수가 넘어야 하는데 말이다.

 

Int값의 할당될 수 있는 크기가 넘어가 버리는 현상을 방지하기 위해

 

그 보다 더 큰 할당량을 가진 Long으로 변환한 것이다.

 

Long으로 변환하니 정수 오버플로우 현상이 사라져,

 

올바른 값이 나오는 것을 확인할 수 있었다.

 

 

코딩 테스트를 하면서 코틀린에 대해 알아가게 된다.