[프로그래머스] N으로 표현 | kotlin

문제 설명

아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.

• 12 = 5 + 5 + (5 / 5) + (5 / 5)
• 12 = 55 / 5 + 5 / 5
• 12 = (55 + 5) / 5

5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.

 

제한사항
N은 1 이상 9 이하입니다.
number는 1 이상 32,000 이하입니다.
수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
최솟값이 8보다 크면 -1을 return 합니다.

---

풀이

배열 설정

val dp= Array(9){mutableSetOf<Int>()}

• dp[i] : N을 i번 사용하여 나오는 숫자들의 집합 저장

첫번째 for문

for(i in 1 until 9){
	dp[i].add((N.toString().repeat(i)).toInt())

• N사용 횟수의 최대 = 8 이므로 1~8까지 반복
• 먼저 N을 i번 반복한 수를 dp[i]에 추가한다.

연산

for(j in 1 .. i/2){
	for(dpj in dp[j]){
		for(dpji in dp[i-j]){
			dp[i].add(dpj+dpji)
			dp[i].add(dpj*dpji)
			if(dpj - dpji != 0){
				dp[i].add(abs(dpj-dpji))   
			}
			if(dpji != 0){
				dp[i].add(dpj/dpji)
			}
			if(dpj != 0){
				dp[i].add(dpji/dpj)
			}
		}
	}
}

• `for(j in 1 .. i/2)`
  • 예시 : dp[3]
    • dp[1] + dp[2] = dp[2] + dp[1]
    • dp[1] * dp[2] = dp[2] * dp[1]
    • dp[1] - dp[2] || dp[2] - dp[1] ( 둘 중에 하나는 음수 || 둘다 0 )
    • dp[1] / dp[2]
    • dp[2] / dp[1]
  • 만약 반복문을 1 until i 로 설정할 경우 덧셈과 곱셈에서 중복된 값을 도출하게 된다.
  • 뺄셈의 경우 문제 조건에 number 가 양수라는 조건이 있기 때문에 연산결과가 양수일 때 유효한 값이다.
  • 따라서 i/2 까지 반복하여 중복된 연산을 수행하지 않도록 설정한다.

결과값

if(dp[i].contains(number)){
	return i
}

• 연산 후 결과 중에 number가 존재한다면 i를 return하며 종료한다.

---

전체 코드

import kotlin.math.abs

class Solution {
    fun solution(N: Int, number: Int): Int {
        val dp= Array(9){mutableSetOf<Int>()} //N을 i번 사용하여 나온 수의 집합
        
        for(i in 1 until 9){
            dp[i].add((N.toString().repeat(i)).toInt()) // N, NN, NNN, ...
            
            for(j in 1 .. i/2){ //중복 연산 제거를 위해 i/2까지 수행
                for(dpj in dp[j]){
                    for(dpijin dp[i-j]){
                        dp[i].add(dpj+dpij)
                        dp[i].add(dpj*dpij)
                        if(dpj - dpij != 0){ //뺄셈 결과가 0인 경우 제외
                            dp[i].add(abs(dpj-dpij))   
                        }
                        if(dpji != 0){ //divisor == 0 인 경우 제외
                            dp[i].add(dpj/dpij)
                        }
                        if(dpj != 0){
                            dp[i].add(dpij/dpj)
                        }
                    }
                }
            }
            if(dp[i].contains(number)){ //연산 결과에 number가 포함되어 있다면 종료
                return i
            }
        }
        return -1 // N을 8번 사용하여 얻은 연산 결과에 number가 없으므로 return -1
    }
}

 

문제 링크