384. Shuffle an Array

Shuffle an Array - LeetCode

 

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

세상에는 다양한 문제를 해결하기 위해 만들어진 알고리즘이 많이 있는 것 같다.