C++로 해결하는 아름다운 배열(Beautiful Array) 문제

문제 개요

고정된 값 N이 주어졌을 때, 배열 A가 1부터 N까지의 정수로 이루어진 순열(permutation)이면서 다음 조건을 만족하면 이를 '아름다운 배열(Beautiful Array)'이라고 정의합니다.

모든 i < j에 대하여, i < k < j를 만족하면서 A[k] × 2 = A[i] + A[j]가 성립하는 k가 존재하지 않아야 합니다.

쉽게 풀어 설명하면, 배열에서 임의의 세 원소를 순서대로 골랐을 때 가운데 값이 양쪽 끝 값의 평균이 되는 경우, 즉 세 값이 등차수열 관계로 배치되는 경우가 없어야 한다는 의미입니다.

N이 주어지면 이 조건을 만족하는 아름다운 배열 A를 아무거나 하나 찾아 반환하면 됩니다. 예를 들어 N = 5라면 [3, 1, 2, 5, 4] 또는 [1, 5, 3, 2, 4] 같은 배열이 유효한 답이 됩니다.

핵심 아이디어: 홀수와 짝수의 분리

이 문제는 분할 정복(Divide and Conquer) 관점에서 접근하면 우아하게 해결할 수 있습니다.

어떤 배열이 아름다운 배열이라면, 각 원소 x를 2x − 1(홀수) 또는 2x(짝수)로 변환한 배열 역시 아름다운 배열입니다.
홀수들만 모은 블록과 짝수들만 모은 블록을 이어 붙여도 여전히 아름다운 배열입니다. 홀수 + 짝수 = 홀수이지만 2 × A[k]는 항상 짝수이므로, 서로 다른 두 블록에 걸쳐 등차 관계가 성립하는 일은 없기 때문입니다.

따라서 [1]에서 출발하여 매 단계마다 기존 원소들을 홀수(2x − 1)와 짝수(2x) 형태로 확장하고, N보다 큰 값은 제외하면 원하는 길이의 아름다운 배열을 얻을 수 있습니다.

알고리즘 단계

배열 ret를 생성하고 1을 삽입합니다.
ret의 크기가 N보다 작은 동안 다음 과정을 반복합니다.
- 새로운 배열 temp를 만듭니다.
- ret의 모든 원소 x에 대해 2x − 1 ≤ N이면 temp에 추가합니다(홀수 처리).
- ret의 모든 원소 x에 대해 2x ≤ N이면 temp에 추가합니다(짝수 처리).
- ret := temp로 갱신합니다.
ret를 반환합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector<int> beautifulArray(int N) {
        vector <int> ret;
        ret.push_back(1);
        while(ret.size() < N){
            vector <int> temp;
            for(int i = 0; i < ret.size(); i++){
                if(ret[i] * 2 - 1 <= N) temp.push_back(ret[i] * 2 - 1);
            }
            for(int i = 0; i < ret.size(); i++){
                if(ret[i] * 2 <= N)temp.push_back(ret[i] * 2 );
            }
            ret = temp;
        }
        return ret;
    }
};
main(){
    Solution ob;
    print_vector(ob.beautifulArray(5));
}

입력

출력

[1,5,3,2,4]

N = 5일 때 동작 과정

1단계: [1]
2단계: [1, 2]
3단계: [1, 3, 2, 4]
4단계: [1, 5, 3, 2, 4] → 최종 결과

각 단계에서 이전 배열의 원소들이 홀수 블록과 짝수 블록으로 나뉘어 확장되며, N보다 큰 값은 자동으로 걸러집니다. 최종적으로 얻은 [1, 5, 3, 2, 4]는 어떤 세 원소도 등차수열 관계로 배치되지 않으므로 아름다운 배열의 조건을 만족합니다.

복잡도 분석

반복문은 배열의 크기가 두 배씩 늘어나므로 O(log N)번 수행되고, 각 반복에서 최대 N개의 원소를 처리하므로 전체 시간 복잡도는 O(N log N)입니다. 사용되는 공간은 결과 배열을 포함하여 O(N)입니다.

C++로 해결하는 아름다운 배열(Beautiful Array) 문제 – 분할 정복 접근법