384. Shuffle an Array
[Shuffle an Array - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com](https://leetcode.com/problems/shuffle-an-array/)
class Solution:
def __init__(self, nums: List[int]):
def reset(self) -> List[int]:
"""
Resets the array to its original configuration and return it.
"""
def shuffle(self) -> List[int]:
"""
Returns a random shuffling of the array.
"""
# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()
위 메서드를 구현하면 되는 문제다.
1. Python 치트키
from typing import *
import random
class Solution:
def __init__(self, nums: List[int]):
self.nums = nums
def reset(self) -> List[int]:
"""
Resets the array to its original configuration and return it.
"""
return self.nums
def shuffle(self) -> List[int]:
"""
Returns a random shuffling of the array.
"""
return random.sample(self.nums, len(self.nums))
random 모듈의 sapmle 메서드를 쓰면 어떤 입력값에 대해서 어떤 길이만큼의 랜덤 한 값을 반환한다.
내장 함수 모듈을 적극적으로 사용했기 때문에 가장 빠르다.
2. Fisher-Yates Algorithm
from typing import *
from copy import deepcopy
import random
class Solution:
def __init__(self, nums: List[int]):
self.nums = nums
def reset(self) -> List[int]:
"""
Resets the array to its original configuration and return it.
"""
return self.nums
def shuffle(self) -> List[int]:
"""
Returns a random shuffling of the array.
"""
temp = deepcopy(self.nums)
for i in range(len(temp)):
random_index = random.randint(i, len(self.nums) - 1)
temp[random_index], temp[i] = temp[i], temp[random_index]
return temp
문제의 출제 의도는 Fisher-Yates Algorithm 알고리즘의 구현이다.
보통 랜덤 음악 재생하기 같은 곳에 사용하는 알고리즘이라고 한다.
from typing import *
from copy import deepcopy
import random
class Solution:
def __init__(self, nums: List[int]):
self.nums = nums
def reset(self) -> List[int]:
"""
Resets the array to its original configuration and return it.
"""
return self.nums
def shuffle(self) -> List[int]:
"""
Returns a random shuffling of the array.
"""
# temp = deepcopy(self.nums)
temp = self.nums[:]
for i in range(len(temp)):
random_index = random.randint(i, len(self.nums) - 1)
temp[random_index], temp[i] = temp[i], temp[random_index]
return temp
위 코드와 완벽히 동일한데 temp에 값을 할당할 때 deepcopy가 아니라 python에서 list를 복사할 때 간간히 쓰는 문법을 통해서 할당해줬다. 그러니깐 속도가 빨라졌다. 아무래도 deepcopy가 훨씬 더 무거운 작업인 것 같은데 실제로 내부 구현에서 어떻게 차이가 나는지는 공부를 해봐야겠다.
[Shuffle Algorithm : 무작위로 섞기 알고리즘 - Fisher-Yates Shuffle & Knuth Shuffle
Dana Daheen Lee #iOS #Swift #CleanCode #Programming
daheenallwhite.github.io](https://daheenallwhite.github.io/programming/algorithm/2019/06/27/Shuffle-Algorithm-Fisher-Yates/)
세상에는 다양한 문제를 해결하기 위해 만들어진 알고리즘이 많이 있는 것 같다.