🍢 초보자 친화 가이드 'Partitioning Into Minimum Number Of Deci-Binary Numbers' - 문제 1689 (C++, Python, JavaScript)

Source: Dev.to

Problem Summary

주어진 것:
매우 큰 양의 정수를 나타내는 문자열 n.

목표:
n을 합으로 만들 수 있는 데시-바이너리 숫자(숫자 0과 1만으로 이루어진 수)의 최소 개수를 찾는다.

Intuition

덧셈은 자리마다 이루어진다. 데시-바이너리 수는 각 십진 자리에서 0 또는 1만 기여할 수 있다.

• 일의 자리에서 7이라는 숫자가 있다면, 7을 만들기 위해서는 최소 7개의 데시-바이너리 수가 필요하다 (1을 7번 더해야 함).
• 다른 자리의 숫자(2나 3 등)도 같은 원리로, 해당 자리에서 0을 사용하는 수들을 포함해 만족시킬 수 있다.

따라서 제한 요소는 문자열에 있는 가장 큰 숫자가 된다.
문자열에 9가 있으면 9개의 데시-바이너리 수가 필요하고, 가장 큰 숫자가 3이면 3개의 수가 필요하다.

Walkthrough: Understanding the Examples

Example 1: n = 32

• 자리수: 3(십의 자리)와 2(일의 자리).
• 십의 자리에서 최소 세 개의 1이 필요 → 10 + 10 + 10.
• 일의 자리에서 두 개의 1이 필요 → 11 + 11 + 10 = 32.
• 사용된 총 수: 3(가장 큰 자리수).

Example 2: n = 82734

• 자리수: 8, 2, 7, 3, 4.
• 가장 큰 숫자는 8.
• 8개의 별도 수가 필요하고, 다른 자리들은 ≤ 8 개의 1을 사용해 만들 수 있다.
• 결과: 8.

Code Blocks

C++

class Solution {
public:
    int minPartitions(string n) {
        int maxi = 0;
        for (char c : n) {
            // Convert character to integer and track the maximum
            if (maxi  int:
        # The result is simply the maximum digit in the string
        # We convert the characters to integers to find the max
        return int(max(n))

JavaScript

/**
 * @param {string} n
 * @return {number}
 */
var minPartitions = function(n) {
    let maxi = 0;
    for (let i = 0; i  maxi) {
            maxi = digit;
        }
        // Optimization: if we find a 9, we can stop early
        if (maxi === 9) return 9;
    }
    return maxi;
};

Key Takeaways

• Greedy Logic: 데이터 집합에서 가장 큰 값이 전체 집합에 필요한 조건을 결정하는 경우가 많다.
• String Manipulation: 표준 정수 범위(10^{100000})를 초과하는 거대한 숫자는 문자열로 다룬다.
• Complexity: 해결 방법은 O(n) 시간(여기서 n은 문자열 길이)과 O(1) 추가 공간을 사용한다.

Final Thoughts

이 문제는 기술 면접에서 “아하!” 순간을 제공한다. 동적 프로그래밍이나 분할 문제처럼 보일 수 있지만, 실제로는 관찰력 테스트이다. 실제 소프트웨어 엔지니어링에서는 자원 할당과 유사한데, 병렬 작업 전체 실행 시간은 가장 오래 걸리는 단일 작업에 의해 제한되듯이, 우리의 합도 가장 큰 자리수에 의해 제한된다.