[ Leetcode ] 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers - Java

 

A decimal number is called deci-binary if each of its digits is either 0 or 1 without any leading zeros. For example, 101 and 1100 are deci-binary, while 112 and 3001 are not.

Given a string n that represents a positive decimal integer, return the minimum number of positive deci-binary numbers needed so that they sum up to n.

 

Example 1:

 
 Input: n = "32" 
 Output: 3 
 Explanation: 10 + 11 + 11 = 32
 

Example 2:

 
 Input: n = "82734" 
 Output: 8
 

Example 3:

 
 Input: n = "27346209830709182346" 
 Output: 9
 

 

Constraints:

• 1 <= n.length <= 105
• n consists of only digits.
• n does not contain any leading zeros and represents a positive integer.

 

Solution

 
 import java.math.BigInteger;
 class Solution {
    public int minPartitions(String n) {
        int count = 0;
        
        for(int i=9; i>0; i--){
            if(n.indexOf(String.valueOf(i)) > -1){
                count = i;
                break;
            }
        }
        return count;
    }
 }
 

1. 처음엔 1을 n개의 숫자대로 곱해서 나누고 몫을 max에 더한뒤 나머지를 또 나누었는데

숫자가 너무 크게나왔다

 

2. 생각해보니 굳이 꽉찬 바이너리 값(111111...)으로 할 필요 없이 최대 숫자로 나눌 수 있지 않을까?

어짜피 제일 큰수보다는 크거나 같을 것이다

32 -> 10*3 + 1*2-> 11*2 + 10

8213 -> 1000*8 + 100*2 + 10*1 + 1*3 -> 합치면 어쨌든 8번보단 커야한다 (1000이 최소로 8번 필요하다)

-> 다른건 8에 묻어가면 가능

 

3. 10진수에서 최대 숫자인 9부터 하나씩 내려가며 작은 것을 찾는다 

찾으면 그 값이 최소로 사용하는 count