leetcode 932 - Beautiful Array

https://leetcode.com/problems/beautiful-array/

풀이

$i < k < j$ 일 때 $2\cdot A[k] = A[i] + A[j]$ 를 만족하는 i, k, j가 없는 배열을 구해야 한다.

 

길이 n짜리 배열 [1, 2, 3, ..., n]이 있을 때 이 조건을 만족하는 배열을 찾기 위해 문제를 나눌 수 있다.

[1, 3, 5, ..., (n+1)/2] 배열과 [2, 4, 6, ..., n/2]로 문제를 나눈 다음에 각 배열의 beautiful array를 구했다고 생각해보자.

각 배열 안에서는 정의 그대로 위 조건에 해당하는 i, k, j가 없다. 이때 두 배열을 concat 한 배열에도 그런 i, k, j는 없음이 보장된다. 앞 배열에 i, 뒷 배열에 j가 있을 때 A[i] + A[j]는 홀수인데 임의의 A[k] * 2는 짝수이기 때문이다.

 

[1, 3, 5, ...(n+1)/2], [2, 4, 6, ..., n/2] 배열의 beautiful array를 구하기 위해 또 나눈다면 앞에 예로 든 홀수/짝수가 맞지 않게 되니 더 일반화해서 $a_n = a + d\cdot(n-1)$ 로 두어도 마찬가지이다.

 

[1, 5, 9, ...] 은 $a_n = 1 + 4\cdot(n-1)$이고, [3, 7, 11, ...]은 $a_n = 3 + 4\cdot(n-1)$ 이다.

앞에서 i, 뒤에서 j를 꺼낸 경우 $A[i] + A[j] = 1 + 4\cdot(i-1) + 3 + 4\cdot(j-1)$ = $4\cdot(i+j-1)$ 로 4의 배수가 나온다. 하지만 앞이든 뒤든 임의의 k번째 값에 x2를 해도 4의 배수는 절대 나오지 않는다.

 

 

이렇게 단순히 두 배열로 나눠서 concat 하는 것 만으로 분할 정복이 된다. n이 1인 경우는 [1] 임이 자명하기 때문에 n = 1이 될 때까지 문제를 나누면 된다. 여기에 중복된 연산을 방지하기 위해 캐시를 추가하면 더 효율적으로 구할 수 있다.

 

 

 

코드

class Solution {
public:
    map<int, vector<int>> cache;
    vector<int> beautifulArray(int N) {
        return find(N);
    }
    
    vector<int> find(int N) {
        if(cache.find(N) != cache.end()) {
            return cache[N];
        }
        if(N == 1) {
            return vector<int>{1};
        }
        
        vector<int> ans;
        vector<int> leftHalf = find((N+1)/2);
        vector<int> rightHalf = find(N/2);
        for(int num: leftHalf) {
            ans.push_back(num*2 - 1);
        }
        for(int num: rightHalf) {
            ans.push_back(num*2);
        }
        
        cache[N] = ans;
        return ans;
    }
};