[LeetCoe] 932. Beautiful Array

문제 출처: https://leetcode.com/problems/beautiful-array/

Beautiful Array - LeetCode

 

문제

n의 크기를 갖는 배열 nums가 다음의 규칙을 따르는 1, 2, ..., n으로 구성된 순열이라면 아름답다(beautiful)고 말할 수 있다:

• 모든 i < j 에 대해서, k가 i < k <j 일 때, 2 * nums[k] = nums[i] + num[j]인 경우가 존재하지 않는다.

n이 주어지면, 아름다운 배열 nums를 반환하라. (답이 존재하지 않는 경우는 없다.)

 

예제

Input: n = 4
Output: [2,1,4,3]

Input: n = 5
Output: [3,1,2,5,4]

 

풀이

이 문제를 Brute Force하게 접근한다고 하면, 순열을 구하는 것은 둘째 치고, 구해진 순열마다 2 * nums[k] = nums[i] + num[j] 조건을 체크하기 위해서 n3의 연산을 수행해야 하기 때문에 비효율적인 방법이라는 결론에 쉽게 도달할 수 있다.

 

먼저, 순열에 존재해서는 안되는 케이스에 어떤 패턴이 존재하는 것은 아닌지 보기 위해서 몇 가지 케이스를 나열해 보았다.

k	2 * k	2 * k= i + j 인 [i, j]
1	2	X
2	4	[1, 3]
3	6	[1, 5], [2, 4]
4	8	[1, 7], [2, 6], [3, 5]
5	10	[1, 9], [2, 8], [3, 7], [4, 6]

위의 표를 살펴보면, [i, j] 쌍에 대해서 i가 홀수라면 j도 홀수이고, i가 짝수라면 j도 짝수인 상황을 발견할 수 있다. 확장시켜 생각해보면, 결국 홀수가 홀수를 부르고, 짝수가 짝수를 부르는 상황임을 알 수 있다. 이 말의 의미를 파악하기 위해서 n = 5 인 상황을 생각해보자.

n = 5

1) 숫자 1: 

	[1]

2) 숫자 2:
    - 제약 사항: [1, 3]
    - [1, 3] 사이에 2가 위치하면 X: 3을 1 옆에 삽입하고, 그 옆에 2를 위치
    
    [1, 3, 2]
    
3) 숫자 3:
    -제약 사항: [1, 5], [2, 4]

3) 숫자 4:
    - 제약 사항: [1, 7], [2, 6], [3, 5]
    - 6, 7 > n: 고려 대상 X
    - [3, 5] 사이에 4가 위치하면 X: 현재 배열에 위치해있는 3 옆에 5를 삽입 후, 4를 마지막에 위치
    
    [1, 3, 5, 2, 4] => 숫자 3의 제약 사항을 위배([1, 5]사이에 3이 위치), 올바르게 재배치 필요
    
    [1, 5, 3, 2, 4]

※ 위 예시에서의 설명은 마지막에 얻어지는 배열이 문제에서 요구하는 배열임을 보여주기 위한 설명일 뿐, 실제 작성할 알고리즘과는 거리가 있다.

 

결과적으로 위 내용을 통해 보여주고자 하는 것은 마지막에 얻어진 배열 [1, 5, 3, 2, 4]의 형태이다. 인덱스 0~2까지의 값은 홀수이고, 3~4의 값은 짝수이다.

 

이러한 형태를 따르는 아름다운(?) 배열을 n의 값에 따라 나열해보면 다음과 같다.

n	Beautiful Array
1	[1]
2	[1, 2]
3	[1, 3, 2]
4	[1, 3, 2, 4]
5	[1, 5, 3, 2, 4]

현재 나열된 Beautiful Array에서 한 가지 패턴을 볼 수 있다. 바로, n-1의 Beautiful Array를 통해서 n의 Beautiful Array를 만들 수 있다는 것이다. 그 규칙은 다음과 같다.

• n-1의 모든 원소를 x라 할 때,
  • (2 * x) -1 을 한 값을 odds 라는 배열에 넣는다.
  • (2 * x) 을 한 값을 evens 라는 배열에 넣는다.
  • 단, 위 계산에서 얻어지는 값이 n보다 크다면 그 값은 무시함
• 얻은 두 배열(odds, evens)을 합한다. (순서 주의)

여기서 한가지 추가하면, n에서의 Beautiful Array를 위해 굳이 n-1을 참조할 필요가 없다. 더 작은 n / 2 의 Beautiful Array를 참조해도 된다(n이 홀수일 때는 (n // 2) + 1). 이것이 가능한 이유는 odds와 evens를 얻을 때, 2를 곱하는 연산이 수행되기 때문이다.

 

지금까지의 내용을 코드로 작성해보면 아래와 같다.

var beautifulArray = function(n) {
    if (n == 1) { return [1]; }
    
    const prevN = n % 2 == 1 ? Math.floor(n/2)+1 : n/2;
    const prevArr = beautifulArray(prevN);
    
    const ans = [];
    for (let val of prevArr) {
        if (2*val - 1 <= n) { ans.push(2*val - 1); }
    }
    for (let val of prevArr) {
        if (2*val <= n) { ans.push(2*val); }
    }
    return ans;
};

 

Github: 932.js

GitHub - opwe37/Algorithm-Study