[Algorithm][LeetCode 1920] buildArray

배열 인덱스를 활용한 간단한 배열 구성 문제 - buildArray

LeetCode의 배열 문제 중 하나인 “Build Array from Permutation” 문제를 정리해보았습니다.

문제 설명

0부터 시작하는 순열 배열 nums가 주어졌을 때, ans[i] = nums[nums[i]]가 되도록 배열 ans를 구성하여 반환하는 문제입니다.

여기서 0 기반 순열(zero-based permutation)은 0부터 nums.length - 1까지의 정수를 중복 없이 포함한 배열을 의미합니다.

예제 1

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

설명:
ans = [
  nums[nums[0]], // nums[0] = 0 → nums[0] = 0
  nums[nums[1]], // nums[1] = 2 → nums[2] = 1
  nums[nums[2]], // nums[2] = 1 → nums[1] = 2
  nums[nums[3]], // nums[3] = 5 → nums[5] = 4
  nums[nums[4]], // nums[4] = 3 → nums[3] = 5
  nums[nums[5]]  // nums[5] = 4 → nums[4] = 3
]

예제 2

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

풀이 1 - 보조 배열 사용 (시간복잡도 O(N), 공간복잡도 O(N))

배열의 인덱스를 사용하면 O(1) 시간에 요소에 접근할 수 있기 때문에 반복문을 통해 ans[i] = nums[nums[i]]를 그대로 구현할 수 있습니다.

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var buildArray = function(nums) {
    const ans = [];
    for (let i = 0; i < nums.length; i++) {
        ans.push(nums[nums[i]]);
    }
    return ans;
};

풀이 2 - in-place 방식 (시간복잡도 O(N), 공간복잡도 O(1))

배열의 공간 복잡도를 줄이기 위해 기존 nums 배열 자체를 최종 결과 배열로 변형하는 방법입니다. 단, 이 방식은 기존 배열을 변경해도 되는 경우에만 사용할 수 있습니다.

핵심 아이디어는 기존 값(nums[i])과 미래 값(nums[nums[i]])을 하나의 숫자에 동시에 저장하는 것입니다.

왜 인코딩이 필요한가?

단순히 nums[i] = nums[nums[i]]로 할 경우, 기존의 nums[i] 값이 손실되어 이후에 필요한 nums[nums[i]] 계산이 틀어지게 됩니다. 이를 해결하기 위해 한 숫자에 두 값을 인코딩합니다:

nums[i] = nums[i] + n * (nums[nums[i]] % n)

- n은 배열의 길이이며,
- nums[nums[i]] % n을 통해 원래의 값을 추출할 수 있습니다.
- 이렇게 하면 기존 값은 nums[i] % n, 미래 값은 Math.floor(nums[i] / n)으로 각각 분리할 수 있습니다.

전체 코드

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var buildArray = function(nums) {
    const n = nums.length;

    // 1단계: 미래 값을 인코딩하여 현재 값에 덧붙임
    for (let i = 0; i < n; i++) {
        nums[i] = nums[i] + n * (nums[nums[i]] % n);
    }

    // 2단계: 미래 값만 추출하여 덮어쓰기
    for (let i = 0; i < n; i++) {
        nums[i] = Math.floor(nums[i] / n);
    }

    return nums;
};

정리

• 보조 배열을 사용하면 구현은 간단하지만 추가 메모리를 사용하게 됩니다.
• in-place 방식은 메모리 사용을 줄일 수 있지만, 수학적 인코딩/디코딩 기법이 필요합니다.
• 이 문제처럼 값의 범위가 제한되어 있을 때(in 0 ~ n-1), 두 값을 한 숫자에 넣는 방식이 특히 유용합니다.