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

문제 요약

• 알고리즘 분류: 그리디, 수학
• 난이도: Medium
• 문제내용:
  • 각 자리수는 0과 1만 올수 있다.
  • 숫자 N을 주어 줬을때 0, 1만 오는10진수 조합된 숫자로 최소 몇번 더하면 되는지 구하여라.
• 사이트 주소: https://leetcode.com/problems/partitioning-into-minimum-number-of-deci-binary-numbers/description/

문제풀이

 이번 문제에는 그리디 문제이다. 그리디 관련 자세한 내용은 아래 글에서 참고 하면된다.

https://jih3508.tistory.com/70

[알고리즘 이론] 그리디(Greedy)

문제 접근방법

  이번 문제는 간단하게 풀수 있는 문제 이다.  그이유는 각 자리수중 큰 값만 구하면 된다. 0과 1만 되어 있는 숫자중 최대 값이 나올라면 큰 값만큼 1씩 더하면 된다. 나머지 자리는 0과 1 중 어떤한 조합이 와도 가장 높은 수만큼 1의 개수만 채우면 된다. 그러면 N의 정수 자리수만큼 탐색 하기 때문에 시간 복잡도는 O(N)만큼 나온다.

Code

Python

class Solution:
    def minPartitions(self, n: str) -> int:
        for num in range(9, 0, -1):
            if str(num) in n:
                return num

Java

class Solution {
   public int minPartitions(String n) {

        char[] numbers = n.toCharArray();

        char maxNum = '0';
        for (char number : numbers) {
            if(number > maxNum){
                maxNum = number;
            }
        }

        return (int) (maxNum - '0');
    }
}