Shuffle

코드 작성하는 인터뷰에 쉽지만 자주 나는 shuffle 문제를 정리 해 보기로 한다.

방법을 알면 쉽지만, 모르면 까다로울 수 있다. 

 

Q. 카드가 n 장 주어진다. 이때 이 카드를 랜덤하게 shuffle해서 반환하라. 

 

Solution. 

 random을 활용해야 하는 것은 확실하다. 

직관적으로 생각해 보면, 루프를 n 번 돌며 랜덤을 생성하고, 나왔던 수가 나온다면 다시 랜덤 번호 생성을 하면 될 것같다. 

이 방법은 최적일 때 O(N)이지만, 최적일 확률은 거의 없다. 

따라서 다른 방법을 생각해 본다. 

 

랜덤한 위치의 카드를 하나 고른다. (1 ~ n 까지의 수 중 하나의 random 번호를 생성한다. )

이 카드를 0번 위치의 카드와 교체한다. 

다시 1번부터 랜덤한 위치의 카드를 고른다. 

이 카드를 1번 위치의 카드와 교체한다. 

이런식으로 n 번 수행하면 O(N)에 셔플이 가능해 진다. 

 

public static void Shuffle(int n)
{
    System.Random random = new System.Random();
    List<int> cards = new List<int>();
    for(int k = 0; k < n ; ++k)
        cards.Add(k);

    for(int k = 0; k < n; ++k)
    {
        int idxRand = random.Next(k, n);
        int temp = cards[idxRand];
        cards[idxRand] = cards[k];
        cards[k] = temp;
    }

    // debug print to check.
    for(int k = 0; k < n; ++k)
        Console.WriteLine(cards[k]);
}