C++로 이진 배열을 아름다운 배열로 만들기 위한 최소 연산 횟수 구하기

이 문제에서는 0과 1로만 구성된 길이 n의 이진 배열 bin[]이 주어지며, 우리의 목표는 이 배열을 아름다운 배열(Beautiful Array)로 만들기 위해 필요한 최소 연산 횟수를 구하는 것입니다.

아름다운 배열이란 0과 1이 서로 교대로 반복되는 특별한 형태의 이진 배열을 의미합니다.

문제 설명

배열을 아름다운 배열로 만들기 위해 필요한 연산 횟수를 구해야 합니다. 하나의 연산은 다음 세 단계로 구성됩니다.

1단계 — 배열을 두 부분으로 자릅니다.
2단계 — 두 부분 중 하나를 뒤집습니다(역순으로 변경).
3단계 — 잘린 두 부분을 다시 합칩니다.

이러한 연산을 반복 수행하여 배열이 아름다운 배열이 될 때까지 필요한 최소 연산 횟수를 계산하면 됩니다.

예제로 문제 이해하기

입력

bin[] = {1, 0, 1, 0, 0, 1}

출력

설명

배열을 잘라 부분 배열 bin[4, 5]를 만든 뒤, 이를 뒤집고 다시 합치면 한 번의 연산으로 아름다운 배열을 만들 수 있습니다.

해결 접근 방식

이 문제의 해법은 연속된 0의 개수를 세는 것에 기반합니다. 즉, 최소 연산 횟수는 연속된 0이 나타나는 횟수와 같습니다. 기본 케이스는 다음과 같습니다.

배열의 크기가 1이라면 이미 아름다운 배열입니다.
배열의 크기가 홀수라면 절대 아름다운 배열이 될 수 없습니다.

짝수 길이의 배열에 대해서는 연속된 0(또는 1)의 총 개수를 확인하면 되며, 그 값이 곧 수행해야 할 연산 횟수가 됩니다.

알고리즘

초기화 — zeroCount, oneCount, consZero = 0

1단계 — n == 1이면 0을 반환합니다.
2단계 — n % 2 != 0이면 -1을 반환합니다.
3단계 — i가 0부터 n-1까지 반복합니다.
3.1단계 — bin[i] == 0 && bin[i+1] == 0이면 consZero를 1 증가시킵니다.
4단계 — bin[n-1] == 0 && bin[0] == 0이면 consZero를 1 증가시킵니다.
5단계 — consZero를 반환합니다.

솔루션 구현 예제

#include <iostream>
using namespace std;

int minOperations(int bin[], int n) {
    if(n == 1)
        return 0;
    if(n % 2 != 0)
        return -1;

    int consZero = 0;
    for (int i = 0; i < n; ++i) {
        if (i + 1 < n) {
            if (bin[i] == 0 && bin[i + 1] == 0)
                consZero++;
        }
    }

    if (bin[0] == bin[n - 1] && bin[0] == 0)
        consZero++;

    return consZero;
}

int main() {
    int bin[] = { 1, 0, 1, 0, 0, 1};
    int n = sizeof(bin) / sizeof(bin[0]);
    cout<<"배열을 아름다운 배열로 만들기 위한 최소 연산 횟수: "<<minOperations(bin, n);
    return 0;
}

출력 결과

배열을 아름다운 배열로 만들기 위한 최소 연산 횟수: 1

위 코드는 시간 복잡도 O(n), 공간 복잡도 O(1)로 효율적으로 동작하며, 배열을 한 번만 순회하여 답을 구할 수 있습니다.