[프로그래머스/programmers] N으로 표현 코틀린(kotlin)

1. 문제 설명

 

아래와 같이 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 함수를 작성하세요.

 

2. 제한 사항

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

 

3. 입출력 예

 

N	number	return
5	12	4
2	11	3

 

4. 입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

예제 #2

11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.

 

5. 알고리즘 설명 및 코드 구현

1. dp 를 이용해서 푸는 경우
2. 완전탐색을 이용해서 푸는 경우

   이렇게 총 2가지로 풀 수 있었습니다.

 

 

첫번째 , dp 를 이용해서 푸는 경우

 

N 은 1~9 이며 9일 때는 -1 을 리턴해야합니다. 그러므로 총 N을 8번 사용해서 만들 수 있어야 합니다.

그렇다면 N 을 한번 사용했을 때 , 두번 사용했을 때 가능한 수를 생각해봅시다.

 

N을 1번, [5]

N을 2번, [55 , 5+5, 5-5, 5÷5, 5×5]

 

아직 여기까지는 뭔가 점화식이 생각날거 같으면서도 나지 않아서 한번만 더 세번 사용했을 때를 생각해봤습니다.

 

N을 3번 , [555 , 5+55, 5-55, 5×55, 5÷55, 5+5+5 , 5-5+5 , 5×5+5 , 5÷5+5....]

 

이제 여기서 점화식이 뭔가 보이기 시작했습니다.

 

N을 3번 사용 했을때는 NNN + (N을1번사용한 전체 사칙연산 N을2번사용한 전체) + (N을2번사용한 전체 사칙연산 N을1번사용한 전체) 라는 점화식이 생성됩니다.  

즉 , N을 1번사용한 elements 를 forEach 를 돌리고 안에서 이중으로 N을 2번 사용한 elements 를 forEach 를 돌림으로써 전체 사칙연산을 하고

반대로 N을 2번 사용한 경우 안에서 N을 1번 사용한 경우를 이중 for문을 돌려서 전체 사칙연산을 한번 더 시킵니다.

 

그렇다면 위에서 2번을 사용했을 때도 점화식이 맞게 된다는걸 알 수있습니다.

2번을 사용했을 때는 NN + (N을 1번사용한 전체 사칙연산 N을 1번사용한 전체) 가 성립이 됩니다.

 

이를 바탕으로 코드를 구현하게 되면

 

class Solution {
    
    companion object {
        
        var lists = mutableListOf<MutableList<Int>>()
        var N = 0
        var number = 0
        
        // 처음 N,NN,NNN... 을 담는 변수
         var num : Int = 0
    }
    
    fun solution(N: Int, number: Int): Int {
        // N이랑 number 가 같다면 바로 return시킨다.
        if(N == number) return 1
        
        Solution.N = N
        Solution.number = number
        Solution.lists.add(mutableListOf<Int>())   
        
        for(i in 1 until 9) {
            dfs(i)
            //Bottom-up방식으로 1부터 차례대로 메모이제이션에 채워질때마다 number있는지 확인
            if(Solution.lists[i].contains(number)) {
                return i
            }
        }
               
        return -1
        
    }
    
    private fun dfs(n : Int)  {
                
        // 처음 N,NN,NNN... 을 담는다.
        Solution.num += Solution.N * Math.pow(10.0 , (n-1).toDouble()).toInt()
        Solution.lists.add(mutableListOf<Int>()) 
        Solution.lists[n].add(Solution.num)
        
        // ex. n=3 이라면 nnn 담고나서는 (n-1 사칙연산 n-2) , (n-2 사칙연산 n-1) 이런식을 담으면 전체식을 담게된다.
        for(i in 1 until n) {
            var j : Int = n - i
            
            Solution.lists[i].forEach { n1 ->
                
                Solution.lists[j].forEach { n2 ->
                    
                    Solution.lists[n].add(n1+n2)
                    Solution.lists[n].add(n1*n2)
                    //뺄셈은 앞의 수가 작으면 음수이므로 조건을 추가
                    if(n1 > n2) Solution.lists[n].add(n1-n2)
                    else Solution.lists[n].add(n2-n1)
                    //나눗셈은 나누는 수가 0이면 안되므로 조건 추가
                    if((n1 > n2) && (n2 != 0)) {
                        Solution.lists[n].add(n1/n2)
                    } else if((n2 >= n1) && (n1 != 0)){
                        Solution.lists[n].add(n2/n1)
                    }                     
                }
                
            }
            
        }
    }
     
}

 

 

두번째로는 완전 탐색입니다.

 

완전 탐색은 정말 말그대로 모든 경우의 수를 쭉 탐색을 하면서 number가 있으면 그때의 사용한 N 을 return 하고

쭉 탐색할 동안 못찾는다면 -1 을 return 하는 방식으로 구현했습니다.

 

	class Solution {
	    
	    companion object {
	        // Int.MaxValue 로 놓고 하듯이 처음에 크게 놓고 점점 줄여 최소를 찾는다.
	        var answer = 9
	        
	        var N = 0
	        var number = 0
	    }
	    
	    fun solution(N: Int, number: Int): Int {
	        // N이랑 number 가 같다면 바로 return시킨다.
	        if(N == number) return 1
	        
	        Solution.N = N
	        Solution.number = number
	        dfs(0 , 0)
	        // 8번 돌 동안 못찾았다면 answer = -1 로 해준다.
	        if(answer == 9) answer = -1
	        
	        
	        return answer
	        
	    }
	    
	    
	    fun dfs(count : Int , findValue : Int) {
	            
	        // 값을 찾았으면서 해당 값이 최소카운트 일 때
	        if(findValue == number && answer > count) {
	            answer = count
	            return
	        }
	        // 처음엔 N 이고 count가 증가할수록 NN , NNN 으로 바뀌는 변수      
	        var n = N
	        
	        // 재귀로 dfs 를 돌면서 모든 경우의 수의 사칙연산을 다한다.
	        // 8 - count 를 한 이유는 n 이 점점 N , NN , NNN 으로 붙을 수록 사용한 count 는
	        // 빼고 측정해줘야 길이가 8이 최대로 유지되기 때문이다.
	        for(i in 0 until 8 - count) {
	           dfs( count + i + 1 , findValue + n)
	           dfs( count + i + 1 , findValue - n)
	           dfs( count + i + 1 , findValue * n)
	           dfs( count + i + 1 , findValue / n)
	           // n * Math 가 아닌 N * Math 를 해줘야한다.
	           // n * Math 를 해주면 다음 for 문 index 를 돌 때 예를 들면
	           // 55 + 5 * 10^2 이 되야 할게 55 + 55 * 10^2 이 되버린다.
               // 즉 55 + 500 = 555 로 넘어가야 할 변수가 55 + 5500 이 되버린다. 
	           n += N * Math.pow(10.0 , (i+1).toDouble()).toInt()
	        }
	        
	    }
	    
	}