[프로그래머스] Lv 3. N으로 표현(Kotlin)

코딩테스트 연습 - N으로 표현

 

문제

숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현할 수 있는 방법 중 N 사용횟수의 최솟값을 return하도록 solution 함수를 작성하세요.

 

풀이

이 문제에서는 제한 사항을 볼 필요가 있습니다.

최솟값이 8보다 크면 -1을 return 한다는 점입니다. 즉, 숫자 N을 최대 8번만 사용 가능하다는 것!

 

이 제한사항 덕분에 문제가 훨씬 간편해졌습니다.

저희는 그저 사칙 연산한 결과를 재귀함수로 전달하면서 number를 만들 수 있는지 검사만 해주면 됩니다.

var n = 0
for (i in 1..8) {
    // N숫자 늘리기, 5, 55, 555, 5555 같이
    n = n * 10 + N

    solve(result + n, count + i, N, number) // +
    solve(result - n, count + i, N, number) // -
    solve(result * n, count + i, N, number) // *
    solve(result / n, count + i, N, number) // /
}

재귀의 탈출 시점은 두 가지가 있습니다.

1. 숫자를 8보다 많이 사용한 경우

2. 사칙연산 결과가 number와 같은 경우

// result: 사칙연산 격롸
// count: 사용한 숫자 개수
fun solve(result: Int, count: Int, N: Int, number: Int) {
	if (count > 8) return
   	if (result == number) {
    	return
    }
}

 

코드

import kotlin.math.*

class Solution {
    var answer = 9
    fun solution(N: Int, number: Int): Int {
        solve(0, 0, N, number)
        return if (answer > 8) -1 else answer
    }
    
    fun solve(result: Int, count: Int, N: Int, number: Int) {
        if (count > 8) return
        if (result == number) {
            answer = min(answer, count)
            return
        }
        
        var n = 0
        for (i in 1..8) {
            // N숫자 늘리기, 5, 55, 555, 5555 같이
            n = n * 10 + N
            
            solve(result + n, count + i, N, number) // +
            solve(result - n, count + i, N, number) // -
            solve(result * n, count + i, N, number) // *
            solve(result / n, count + i, N, number) // /
        }
    }
}