Portfolio

Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

Solution(int[] nums) Initializes the object with the integer array nums.

int[] reset() Resets the array to its original configuration and returns it.

int[] shuffle() Returns a random shuffling of the array.

Example 1:


Input
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // Shuffle the array [1,2,3] and return its result.
                       // Any permutation of [1,2,3] must be equally likely to be returned.
                       // Example: return [3, 1, 2]
solution.reset();      // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle();    // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]

Constraints:

1 <= nums.length <= 200

106 <= nums[i] <= 106

All the elements of nums are unique.

At most 5 * 104 calls in total will be made to reset and shuffle.

풀이

은찬


/**
 * @param {number[]} nums
 */
class Solution{
    constructor(nums){
        this.original = [...nums];
        this.nums = nums;
    }
    
    reset() {
        this.nums = [...this.original];

        return this.nums;
    }
    
    shuffle() {
        for(let i = this.nums.length - 1; i > 0; i--){
            const random = Math.floor(Math.random() * (i + 1));
            
            [this.nums[i], this.nums[random]] = [this.nums[random], this.nums[i]];
        }

        return this.nums;
    }
};

재영

✨ 풀이 과정에 대해서 설명해봅시다.

💥 문제의 핵심 알고리즘

알고리즘이라기보다는, 순열을 어떻게 효과적으로 문제에 적용할 수 있느냐가 관건인 문제이다.

🔥 상세 풀이 과정

reset을 위한 originalNums 배열을 생성한다.

shuffle에서의 문제는 결국, 제한 시간 안에 순열을 계속해서 조회하는 로직을 생성할 수 있는지다.

기존에 순열을 만드는 알고리즘은 O(N!)이다. 이는 N = 4를 넘어갔을 때 오히려 O(N^2)보다 비효율적이다. 따라서 이를 최적화해야 한다.

인덱스를 랜덤으로 생성해서, 배열의 스왑을 이용했다. 어차피 셔플이 일어날 때마다, for문으로 스왑하며 새로운 배열을 생성해내면, 주어진 문제를 O(N)만에 해결할 수 있다.


/**
 * @param {number[]} nums
 */
 var Solution = function(nums) {
    this.nums = [...nums];
    this.originalNums = [...nums];
    
    return this;
};

/**
 * @return {number[]}
 */
Solution.prototype.reset = function() {
    return this.originalNums;
};

/**
 * @return {number[]}
 */
Solution.prototype.shuffle = function() {
    const { floor, random } = Math;
    
    for (let i = 0; i < this.nums.length; i += 1) {
        const randomIndex = floor(random()  * this.nums.length);
        [this.nums[i], this.nums[randomIndex]] = [this.nums[randomIndex], this.nums[i]]
    }
    
    return this.nums
};

/** 
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(nums)
 * var param_1 = obj.reset()
 * var param_2 = obj.shuffle()
 */

효성


var Solution = function(nums) {
    this.nums = nums;
    this.arr = [...nums];
};


Solution.prototype.reset = function() {
    return this.nums;
};


Solution.prototype.shuffle = function() {
    const arr = this.arr;
    arr.forEach((_, idx) => {
        const randomIdx = Math.floor(Math.random() * arr.length);
        [arr[randomIdx], arr[idx]] = [arr[idx], arr[randomIdx]];
    });
    
    return this.arr;
};

Shuffle an Array

풀이

✨ 풀이 과정에 대해서 설명해봅시다.