[Codeforces] #2259C - 101 [C++]

문제 링크

---

1. 아이디어

배열의 점수는 양 끝이 1이고 사이가 전부 0인 가장 긴 부분 배열의 길이다. 각 원소가 -1, 0, 1 중 하나인 배열 a에서 -1을 0 또는 1로 채워 이 점수를 최대로 만든 결과를 출력하는 문제다.

이 문제는 그리디한 접근으로 해결했는데, 1 사이에 위치한 -1은 최대한 0으로 바꾸는 것이 이득이라는 점과 가장 바깥쪽 1을 최대한 벌리는 것이 이득이라는 점이다. 이를 위해 배열 양 끝에서부터 0이 아닌 원소가 처음 등장하는 위치를 찾아서 해당 값이 -1이면 1로 바꿨다. 0으로 바꿀 경우 부분 배열 후보가 생기지 않는 것이므로 1로 바꾸는 것이 항상 이득이다. 이렇게 양 끝을 1로 잡았으면 그 사이의 모든 -1은 0으로 바꾸어 부분 배열이 더 쪼개지지 않게 하면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(1)$

($N$ = 모든 테스트 케이스에 걸친 수열 길이의 총합)

---

3. 코드

풀이 [C++]

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

void solve() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int& x : a) cin >> x;

    int s = 0, e = n - 1;
    while (s < n && a[s] == 0) s++;
    while (e >= 0 && a[e] == 0) e--;

    if (s <= e) {
        a[s] = a[e] = 1;
        for (int i = s + 1; i < e; i++) {
            if (a[i] == -1) a[i] = 0;
        }
    }

    for (int x : a) {
        cout << x << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) solve();
}

---