프로그래머스 - 피자나눠먹기(2) [Kotlin]

문제 설명

머쓱이네 피자가게는 피자를 여섯 조각으로 잘라 줍니다. 피자를 나눠먹을 사람의 수 n이 매개변수로 주어질 때, n명이 주문한 피자를 남기지 않고 모두 같은 수의 피자 조각을 먹어야 한다면 최소 몇 판을 시켜야 하는지를 return 하도록 solution 함수를 완성해보세요.

제한 사항

1 ≤ n ≤ 100

접근 방법

해당 문제는 최소공배수를 구해서 6으로 나누면 되겠다고 생각했다. 아직 알린이인 나는 최소공배수를 어떻게 구해야할지 한참을 고민하다가 최소공배수 공식을 찾게 된다...




코드로 최소공배수를 구하는 방법은 최대공약수를 구하여 계산하는 방법인데 최대공약수는 유클리드 호제법을 이용하는 것이 효율적이다. 그 이유는 시간복잡도에서 찾을 수 있다.
최대공약수를 구하는 일반적인 방법으로 2부터 두 자연수 중 작은 자연수까지 모두 나누어보는 방식이 있다. 해당 방법으로 최대공약수를 구할 경우 시간복잡도는 O(n)이 된다.
유클리드 호제법으로 최대공약수를 구할 경우 시간복잡도는 O(log n)이 된다.


유클리드 호제법의 수식은 다음과 같다.

해당 수식을 코드로 표현하면 다음과 같이 표현할 수 있다.

반복문을 이용한 코드

fun gcd(a: Int, b: Int): Int {
    var aa: Int = a
    var bb: Int = b
    while(b != 0) {
        var r: Int = a % b
        aa = b
        bb = r
    }
    return aa
}

재귀를 이용한 코드

fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a%b)

그래서 해당 문제에 이것을 적용하면 다음과 같이 문제를 풀 수 있다.

코드

class Solution {
    fun solution(n: Int): Int = lcm(6, n) / 6

    fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a%b)

    fun lcm(a: Int, b: Int): Int = a * b / gcd(a, b)
}

 

 

 

 

다른 사람의 코드

문제를 풀고 다른 사람의 풀이를 보았는데 새로운 키워드를 발견하였다.

tailrec fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a%b)

tailrec 키워드가 무엇인지 궁금해서 공부한 것을 설명해보고자 한다.

tailrec

tailrec 키워드는 tail recursive를 가리키는 키워드로 꼬리재귀를 사용하는 함수에 사용한다. 이 키워드를 사용하지 않더라도 꼬리재귀를 구현할 수 있는데 이 키워드를 사용하는 것과 안하는 것은 무엇이 차이가 있을까?




가장 큰 차이점은 바로 바이트코드로 변환할 때 생긴다.
tailrec키워드를 사용하지 않은 일반적인 재귀함수는 코드에서 보는 것처럼 바이트코드가 재귀로 호출되게 된다.

>일반 재귀함수

바이트코드를 잘은 모르지만 INVOKESTATIC 이라는 명령어로 함수가 다시 호출되는 것을 볼 수 있다. 이 바이트코드를 자바코드로 디컴파일하면 다음과 같이 나온다.

작성한 것과 같이 똑같이 재귀로 불린다.

>tailrec 재귀함수

이번에는 tailrec 키워드를 사용한 재귀함수를 살펴보자.
tailrec 키워드를 사용한 재귀함수는 바이트코드로 변환될 때 반복문으로 변환되게 된다.


반복문으로 변환되면 좋은 점은??
반복문으로 변환될 경우 재귀함수를 호출하는 것보다 소비되는 스택을 아낄 수 있다. 그래서 tailrec 키워드를 통해 코드는 재귀이지만 보다 적은 자원을 사용하며 함수를 실행할 수 있다.
tailrec 함수의 바이트코드는 다음과 같다.

일반 재귀함수와는 다르게 INVOKESTATIC 명령어가 없어진 것을 볼 수 있다. 이 바이트코드를 자바코드로 디컴파일하면 다음과 같이 나온다.

위에서 적은 반복문을 이용한 코드와 비슷하지 않은가?

정리

이번 문제를 통해 최소공배수와 최대공약수 정도는 기억해주는게 좋다고 생각이 들었다. 특히 유클리드 호제법으로 짠다면 코딩테스트에 더 유익할 것 같다.
또 tailrec 키워드를 공부할 수 있었다. tailrec은 재귀함수 코드를 작성하더라도 바이트코드 변환 시 반복문을 사용하여 스택과 자원을 아낄 수 있다.
알고리즘을 공부하면서 다른 사람의 코드도 보는 것이 공부가 많이 되는 것 같다.