C++로 숫자 문자열을 Y 이하 값으로 분할하는 최소 집합 개수 구하기

문제 개요

연속된 숫자로 이루어진 문자열과 하나의 수 Y가 주어졌을 때, 아래 조건을 모두 만족하는 최소한의 집합 개수를 구하는 것이 이번 문제의 목표입니다.

각 집합은 문자열에서 연속된 숫자들로 구성되어야 합니다.
같은 자릿수는 두 번 이상 사용할 수 없습니다.
집합에 포함된 수는 Y보다 커서는 안 됩니다.

예시

예를 들어 str = "1234"이고 Y = 20이라면, 아래와 같이 세 개의 집합이 만들어지므로 정답은 3입니다.

{12} {3} {4}

"1234"를 그대로 하나의 수로 보면 1234는 Y인 20을 초과하기 때문에, 숫자를 적절히 끊어 각 집합의 값이 Y 이하가 되도록 최소 횟수로 분할해야 합니다.

알고리즘

문자열을 왼쪽부터 한 글자씩 읽으며 누적해서 숫자로 변환합니다.
현재까지 만든 숫자가 Y보다 크지 않으면 플래그 f = 1로 표시하고 계속 진행합니다.
누적한 숫자가 Y를 초과하면, 직전까지 유효한 집합이 존재했는지(f = 1) 확인하여 카운트를 증가시킵니다. 이후 f를 0으로 초기화하고, num을 현재 자릿수 값(s[i] - '0')으로 새로 설정합니다. 만약 단일 자릿수조차 Y보다 크다면 num을 0으로 초기화합니다.
문자열 전체를 순회한 후, 마지막 집합도 유효하다면(f = 1) 카운트를 하나 더 증가시킵니다.

C++ 구현 예제

#include <iostream>
#include <string>
using namespace std;
int getMinSets(string str, int y) {
    int cnt = 0;
    int num = 0;
    int l = str.length();
    int f = 0;
    for (int i = 0; i < l; ++i) {
        num = num * 10 + str[i] - 48;
        if (num <= y) {
            f = 1;
            continue;
        }
        if (f) {
            ++cnt;
        }
        num = str[i] - '0';
        f = 0;
        if (num <= y) {
            f = 1;
        } else {
            num = 0;
        }
    }
    if (f) {
        ++cnt;
    }
    return cnt;
}
int main() {
    string str = "1234";
    int y = 20;
    cout << "Minimum sets = " << getMinSets(str, y) << endl;
    return 0;
}

동작 원리

이 알고리즘은 그리디 방식으로 동작합니다. 문자열을 순회하면서 숫자를 한 자리씩 확장해 가며("1" → "12" → "123") 값이 Y 이하인 동안에는 같은 집합에 계속 포함시킵니다. 확장한 숫자가 Y를 초과하는 순간에는 직전까지의 숫자를 하나의 집합으로 확정하고 카운트를 증가한 뒤, 현재 자릿수부터 새로운 집합을 시작합니다. 이렇게 하면 각 집합을 가능한 한 길게 유지하게 되므로, 결과적으로 필요한 집합의 개수가 최소화됩니다.

시간 복잡도는 문자열을 한 번만 순회하므로 O(n)이며, 추가 메모리 사용량은 상수 수준입니다.

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력을 얻을 수 있습니다.

Minimum sets = 3