HomeAboutMeBlogGuest
© 2025 Sejin Cha. All rights reserved.
Built with Next.js, deployed on Vercel
👻
개발 기록
/
코딩테스트 스터디
코딩테스트 스터디
/
Shuffle an Array

Shuffle an Array

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:
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.
 

풀이

은찬
재영

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

💥 문제의 핵심 알고리즘
알고리즘이라기보다는, 순열을 어떻게 효과적으로 문제에 적용할 수 있느냐가 관건인 문제이다.
 
🔥 상세 풀이 과정
  1. reset을 위한 originalNums 배열을 생성한다.
  1. shuffle에서의 문제는 결국, 제한 시간 안에 순열을 계속해서 조회하는 로직을 생성할 수 있는지다.
  1. 기존에 순열을 만드는 알고리즘은 O(N!)이다. 이는 N = 4를 넘어갔을 때 오히려 O(N^2)보다 비효율적이다. 따라서 이를 최적화해야 한다.
  1. 인덱스를 랜덤으로 생성해서, 배열의 스왑을 이용했다. 어차피 셔플이 일어날 때마다, for문으로 스왑하며 새로운 배열을 생성해내면, 주어진 문제를 O(N)만에 해결할 수 있다.
효성
Link
https://leetcode.com/problems/shuffle-an-array/
Deadline
Mar 5, 2022
Status
Archived
Type
Array
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]
/** * @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; } };
/** * @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; };