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) 접근법과 홀수/짝수 분리를 활용하는 것입니다.
다음과 같은 중요한 성질을 활용합니다:
- 홀수들로만 구성된 아름다운 배열이 있다면, 각 요소에 2를 곱하고 1을 빼서 새로운 홀수 아름다운 배열을 만들 수 있습니다.
- 짝수들로만 구성된 아름다운 배열이 있다면, 각 요소에 2를 곱해서 새로운 짝수 아름다운 배열을 만들 수 있습니다.
- 홀수 아름다운 배열과 짝수 아름다운 배열을 연결하면, 결과도 아름다운 배열이 됩니다.
왜 이런 접근이 효과적일까요? 홀수와 짝수를 분리하면, 홀수 + 짝수 = 홀수이고, 짝수 + 짝수 = 짝수이기 때문에, 두 수의 합의 절반(평균)은 항상 다른 그룹에 속하게 됩니다. 따라서 평균값은 배열 내 다른 요소와 일치할 수 없습니다.
알고리즘 설계
- 기본 케이스: n = 1일 때, [1]을 반환합니다.
- 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
반응형
'알고리즘 > Leetcode' 카테고리의 다른 글
[Leetcode] 1760. Minimum Limit of Balls in a Bag (3) | 2025.06.13 |
---|---|
[Leetcode]2807. Insert Greatest Common Divisors in Linked List (0) | 2025.05.20 |
[Leetcode]1306. Jump Game III (0) | 2025.05.07 |
[Leetcode] 3016. Minimum Number of Pushes to Type Word II (0) | 2025.05.06 |
[Leetcode] 881. Boats to Save People (1) | 2025.04.28 |