인덱스 범위 내 최댓값을 위한 이진 문자열 정렬

문제 설명

0과 1로만 구성된 이진 문자열이 주어지고, 서로 겹치지 않는 M개의 구간 [A₁, B₁], [A₂, B₂], …, [A_M, B_M](단, A ≤ B)이 함께 주어집니다. 임의의 두 구간 i ≠ j에 대해 항상 A_i < B_j 또는 B_j < A_i가 성립하므로, 어떤 두 구간도 서로 겹치지 않습니다.

목표는 다음 두 조건을 동시에 만족하는 유효한 재배열(순열)을 찾는 것입니다.

구간 합 최대화: 주어진 M개의 구간에 포함된 숫자들의 합이 가능한 한 커야 합니다.
사전순 최대: 문자열 전체가 사전순으로 최대가 되어야 합니다. 예를 들어 1100은 1001보다 사전순으로 더 큽니다.

예제

먼저 3번, 4번 위치에 1을 배치하고, 그다음 5번 위치에 마지막 1을 배치합니다. 더 이상 남은 1이 없으므로 최종 문자열은 00111이 됩니다.

위 예제에서는 먼저 1번, 2번 위치에 1을 배치합니다. 이때 1이 하나 더 남아 있으므로, 사전순을 최대화하기 위해 남은 1을 범위 밖의 가장 앞쪽 위치인 3번에 배치하여 재배열을 완성합니다.

접근 방법: 그리디 알고리즘

구간들이 서로 겹치지 않기 때문에, 어느 구간에 1을 배치하든 합에 대한 기여도는 동일하게 1입니다. 따라서 다음과 같은 그리디 전략이 최적임을 보장할 수 있습니다.

1의 개수 세기: 원본 문자열에 있는 1의 총개수를 계산합니다.
구간 우선 채우기: 구간에 속한 위치들을 왼쪽부터 오른쪽으로 탐색하며, 아직 남은 1이 있다면 해당 위치를 1로 채웁니다. 구간 안에 최대한 많은 1을 넣어야 합이 최대가 되고, 그중에서도 왼쪽부터 채워야 사전순이 가장 커집니다.
남은 1 배치: 모든 구간을 채운 뒤에도 1이 남아 있다면, 구간 밖의 위치 중 가장 왼쪽부터 순서대로 배치합니다.

C++ 구현

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    int m;
    cin >> s >> m;

    int n = s.size();
    vector<bool> inRange(n + 1, false);   // 1-indexed

    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        for (int p = a; p <= b; ++p) inRange[p] = true;
    }

    int ones = count(s.begin(), s.end(), '1');
    string res(n, '0');

    // 1단계: 구간에 속한 위치를 왼쪽부터 채움 (합 최대화)
    for (int p = 1; p <= n && ones > 0; ++p) {
        if (inRange[p]) { res[p - 1] = '1'; --ones; }
    }

    // 2단계: 남은 1은 구간 밖 가장 왼쪽부터 배치 (사전순 최대화)
    for (int p = 1; p <= n && ones > 0; ++p) {
        if (!inRange[p]) { res[p - 1] = '1'; --ones; }
    }

    cout << res << endl;
    return 0;
}

복잡도 분석

시간 복잡도: O(N + Σ(B_i − A_i + 1)) — 문자열 길이와 모든 구간 길이의 합에 비례합니다.
공간 복잡도: O(N) — 각 인덱스가 구간에 속하는지 표시하는 배열이 필요합니다.

인덱스 범위 내 최댓값을 위한 이진 문자열 정렬 – C/C++ 그리디 구현

문제 설명

예제

접근 방법: 그리디 알고리즘

C++ 구현

복잡도 분석