Leetcode 932. Beautiful Array

문제

An array nums of length n is beautiful if:

nums is a permutation of the integers in the range [1, n].
For every 0 <= i < j < n, there is no index k with i < k < j where 2 * nums[k] == nums[i] + nums[j].
Given the integer n, return any beautiful array nums of length n. There will be at least one valid answer for the given n.

배열 nums의 길이가 $n$일 때, 다음 조건을 만족하면 beautiful array라고 한다.

1. nums는 $1$부터 $n$까지의 정수를 정확히 한 번씩 포함하는 순열이다.

즉,

2. 모든 인덱스 $i, j$에 대해 $0 \le i < j < n$일 때, 그 사이에 있는 어떤 인덱스 $k$도 다음 조건을 만족하면 안 된다.

이면서 동시에

인 경우가 존재하면 안 된다.

다시 말해, nums[i]와 nums[j] 사이에 있는 값 nums[k]가 두 값의 정확한 평균이 되면 안 된다.

문제는 정수 $n$이 주어졌을 때, 길이가 $n$인 beautiful array nums를 아무거나 하나 반환하는 것이다.

항상 적어도 하나의 정답은 존재한다.

---

예시

n == 4 -> [2, 1, 4, 3]

n == 5 -> [3, 1, 2, 5, 4]

---

제한

$1 \le n \le 1000$

---

풀이

일단 beautiful array가 되는 조건을 살펴보자면

a < b < c 인 세 인덱스에 대해

arr[a] + arr[c] != arr[b] * 2

가 되면 된다, 다만 여기서 알수 있는 사항은 arr[b] * 2 는 2를 곱하니까 반드시 짝수가 만들어진다는 뜻이다!

이 상태에서 만약 내가 [홀수로만 이루어진 beautiful array] + [짝수로만 이루어진 beautiful array] 로 n개의 배열을 만든다면 저 내부에 있는 홀수, 짝수 array만 제대로 beautiful 하다면 이것도 beautiful 할 것이다.

근데 어떻게 홀수로만 이루어진것을 찾을수 있을까? 여기서 하나의 트릭이 나온다.

길이가 3개인 beautiful array [ 이하 ba ], [1, 3, 2] 가 있다.

모든 원소에 곱하기 2를 해보자 -> [2, 6. 4] -> 오! 짝수로만 이루어진 ba가 된다.
여기에 모든 원소에 1을 빼보자 -> [1, 5, 3] -> 홀수로만 이루어진 ba가 된다.

지금까지 찾은 정보를 이용해 재귀로 분할정복을 구현할수 있다.

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        def beautiful(size: int) -> List[int]:
            if size <= 2:
                return [v for v in range(1, size + 1)]

            odd = size // 2 + 1 if size % 2 else size // 2
            even = size // 2

            return [2 * v - 1 for v in beautiful(odd)] + [2 * v for v in beautiful(even)]

        return beautiful(n)