본문 바로가기
알고리즘/Leetcode

[Leetcode]932. Beautiful Array

by 응애~ 개발자 2025. 5. 14.
728x90
반응형

문제 요약

  • 알고리즘 분류: 분할정복
  • 난이도: Medium
  • 문제내용:
    • nums는 [1, n] 범위의 정수들의 순열입니다.
    • 모든 0 <= i < j < n에 대해, i < k < j를 만족하는 인덱스 k 중에서 2 * nums[k] = nums[i] + nums[j]를 만족하는 k가 존재하지 않습니다.
    • 정수 n이 주어졌을 때, 길이가 n인 임의의 아름다운 배열 nums를 반환하세요. 주어진 n에 대해 적어도 하나의 유효한 답이 존재합니다.
  • 사이트 주소: https://leetcode.com/problems/beautiful-array/description/

문제풀이

이 문제를 풀기 위한 핵심 통찰은 분할 정복(Divide and Conquer)을 활용하는 것입니다. 분할 정복에 대한 내용은 아래 글에서 확인 해보면 됩니다.

https://jih3508.tistory.com/282

 

[알고리즘 이론] 분할 정복(Divide and Conquer)

분할 정복(Divide and Conquer) 알고리즘 완벽 가이드1. 분할 정복이란?분할 정복(Divide and Conquer)은 복잡한 문제를 더 작고 관리하기 쉬운 하위 문제들로 나누어 해결하는 알고리즘 패러다임입니다. 이

jih3508.tistory.com

접근 방법

이 문제를 풀기 위한 핵심 통찰은 분할 정복(Divide and Conquer) 접근법과 홀수/짝수 분리를 활용하는 것입니다.

다음과 같은 중요한 성질을 활용합니다:

  1. 홀수들로만 구성된 아름다운 배열이 있다면, 각 요소에 2를 곱하고 1을 빼서 새로운 홀수 아름다운 배열을 만들 수 있습니다.
  2. 짝수들로만 구성된 아름다운 배열이 있다면, 각 요소에 2를 곱해서 새로운 짝수 아름다운 배열을 만들 수 있습니다.
  3. 홀수 아름다운 배열과 짝수 아름다운 배열을 연결하면, 결과도 아름다운 배열이 됩니다.

왜 이런 접근이 효과적일까요? 홀수와 짝수를 분리하면, 홀수 + 짝수 = 홀수이고, 짝수 + 짝수 = 짝수이기 때문에, 두 수의 합의 절반(평균)은 항상 다른 그룹에 속하게 됩니다. 따라서 평균값은 배열 내 다른 요소와 일치할 수 없습니다.

알고리즘 설계

  1. 기본 케이스: n = 1일 때, [1]을 반환합니다.
  2. n에 대한 아름다운 배열을 구하기 위해:
    • 크기가 ⌈n/2⌉인 아름다운 배열(홀수 부분)을 재귀적으로 구합니다.
    • 크기가 ⌊n/2⌋인 아름다운 배열(짝수 부분)을 재귀적으로 구합니다.
    • 홀수 부분의 각 요소 x를 2x-1로 변환합니다.
    • 짝수 부분의 각 요소 x를 2x로 변환합니다.
    • 변환된 홀수 부분과 변환된 짝수 부분을 연결하여 최종 아름다운 배열을 생성합니다.

결론

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 **O(n log n)**입니다:

  • 각 재귀 호출에서 배열의 크기가 절반으로 줄어듭니다.
  • 재귀 트리의 깊이는 O(log n)입니다.
  • 각 수준에서 O(n)의 작업을 수행합니다.

문제는 분할 정복과 수학적 관찰을 기반으로 하여, 일반적인 순열 생성 문제와는 다른 창의적인 접근을 요구합니다.

  • 문제 조건에서 주어진 "중간값 조건"을 피하기 위해 홀수/짝수로 분리
  • 2 * num - 1, 2 * num으로 값 범위 조절
  • 결과적으로 어떠한 세 수 조합도 조건을 위반하지 않음

Code

Python

class Solution:
    def beautifulArray(self, n: int) -> List[int]:
        
        # 기본 케이스: n이 1이면 [1]을 반환합니다.
        if n == 1:
            return [1]

        arr = [0] * n

        # 분할 정복 접근법: 홀수 부분 먼저 계산
        # (n+1)/2는 홀수 요소의 개수입니다. 올림 나눗셈으로 n이 홀수일 때 정확한 값을 얻습니다.
        left = self.beautifulArray((n + 1) // 2)

        index = 0

        # 홀수 부분 처리: 재귀적으로 얻은 결과에 변환을 적용
        # 모든 값 x를 2x-1로 변환하여 홀수로 만듭니다.
        for num in left:
            arr[index] = num * 2 - 1
            index += 1

        # 짝수 부분 계산: n/2는 짝수 요소의 개수입니다.
        right = self.beautifulArray(n // 2)

        # 짝수 부분 처리: 재귀적으로 얻은 결과에 변환을 적용합니다.
        # 모든 값 x를 2x로 변환하여 짝수로 만듭니다.
        for num in right:
            arr[index] = num * 2
            index += 1

        return arr

Java

class Solution {
    public int[] beautifulArray(int n) {

        // 기본 케이스: n이 1이면 [1]을 반환합니다.
        if(n == 1) return new int[] {1};

        // 결과를 저장할 배열을 생성합니다.
        int[] arr = new int[n];

        // 분할 정복 접근법: 홀수 부분 먼저 계산
        // (n+1)/2는 홀수 요소의 개수입니다. 올림 나눗셈으로 n이 홀수일 때 정확한 값을 얻습니다.
        int[] left = beautifulArray((n + 1) / 2);
        int index = 0;

        // 홀수 부분 처리: 재귀적으로 얻은 결과에 변환을 적용합니다.
        // 모든 값 x를 2x-1로 변환하여 홀수로 만듭니다.
        for(int num : left) {
            arr[index++] = num * 2 - 1;
        }

        // 짝수 부분 계산: n/2는 짝수 요소의 개수입니다.
        int[] right = beautifulArray(n / 2);

        // 짝수 부분 처리: 재귀적으로 얻은 결과에 변환을 적용합니다.
        // 모든 값 x를 2x로 변환하여 짝수로 만듭니다.
        for(int num : right) {
            arr[index++] = num * 2;
        }

        // 아름다운 배열을 반환합니다.
        return arr;
    }
}

Javascript

var beautifulArray = function(n) {

    // 기본 케이스: n이 1이면 [1]을 반환합니다.
    if(n === 1)
        return [1];

    // 결과를 저장할 배열을 생성합니다.
    let arr = Array(n);

    // 분할 정복 접근법: 홀수 부분 먼저 계산
    // (n+1)/2는 홀수 요소의 개수입니다. 올림 나눗셈으로 n이 홀수일 때 정확한 값을 얻습니다.
    const left =  beautifulArray(Math.floor((n + 1) / 2) );

    let index = 0;

    // 홀수 부분 처리: 재귀적으로 얻은 결과에 변환을 적용
    // 모든 값 x를 2x-1로 변환하여 홀수로 만듭니다.
    left.forEach((num) => {
        arr[index++] = num * 2 - 1;
    });

    // 짝수 부분 계산: n/2는 짝수 요소의 개수입니다.
    const right =  beautifulArray(Math.floor(n  / 2) );

    // 짝수 부분 처리: 재귀적으로 얻은 결과에 변환을 적용합니다.
    // 모든 값 x를 2x로 변환하여 짝수로 만듭니다.
    right.forEach((num) => {
        arr[index++] = num * 2;
    });

    return arr;
};
728x90
반응형