[C#] 1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

1. 문제

 

 

0과 1로만 이루어졌으면서 0으로는 시작하지 않는 수를 deci-binary라고 한다.

양의 십진수인 n이 string으로 주어진다. 양의 deci-binary들의 합으로 n을 만들어야하는데 이 때 필요한 deci-binary의 최소 갯수를 구하면 된다.

 

 

---

 

2. 풀이 과정

 

9를 만들기 위해서는 1을 9번 더하면 된다.

19를 만들기 위해서는 11을 1번, 1을 8번. 총 9번 더하면 된다.

173을 만들기 위해서는 111을 1번, 11을 2번, 10을 4번. 총 7번을 더하면 된다.

즉 각 자릿수 중 최대값만큼만 더하면 된다.

 

string을 char 배열로 변환 후 char 배열에서 '0'을 빼서 int배열에 int값으로 변환하여 담아주었다.

int배열에서 최댓값을 출력하면 자릿수 중 가장 큰 값이 출력된다.

 

각 자릿수는 9가 최대이므로 for문 중간에 9를 발견했을 때 9를 return 시켜버린다면 무의미한 검사를 줄일 수 있을 것이다.

하지만 for문의 loop 횟수는 10000번이 최대이므로 매번 if문으로 검사하면서 탈출을 시도하는 것이 유의미한것일까 싶어서 주석처리.

 

public class Solution {
    public int MinPartitions(string n) {
        var charArray = n.ToCharArray();
        var intArray = new int[n.Length];

        for(int i = 0, length = n.Length; i < length; ++i)
        {
            intArray[i] = charArray[i] - '0';
            
            // if(intArray[i] == 9)
            // 	return 9;
        }

        return intArray.Max();
    }
}