[Javascript][백준] 1091번 - 카드 섞기

 

문제

이 문제는 단순한 구현 문제이지만, 문제를 올바르게 이해하는 것이 중요합니다. 카드 섞기와 분배 과정을 정확히 파악해야 합니다.

문제 해결의 핵심은 다음과 같은 특성들을 고려하는 것입니다:

1. 사이클 감지: 같은 방법으로 계속 섞다 보면 결국 이전에 나타났던 패턴이 다시 나타납니다.
2. 카드 위치와 플레이어 매핑: 카드가 놓인 위치에 따라 어떤 플레이어에게 분배되는지 결정됩니다. 0, 3, 6... 위치의 카드는 플레이어 0에게, 1, 4, 7... 위치의 카드는 플레이어 1에게, 2, 5, 8... 위치의 카드는 플레이어 2에게 갑니다. 즉, 위치 i의 카드는 플레이어 i % 3에게 분배됩니다.

이 문제를 해결하기 위해 다음과 같은 단계를 거칩니다:

1. 초기 덱 상태 설정 (카드 번호와 위치가 일치)
2. 각 단계마다:
   • 카드를 주어진 방법으로 섞기
   • 올바른 분배인지 확인
   • 이전에 본 패턴인지 확인 (사이클 감지)

 

풀이

• 시간복잡도: O(N² * N!) (N: 카드의 수)

function solution() {
    // 각 플레이어가 받아야 하는 카드 목록
    const playerCards = {};
    for(let i = 0; i < N; i++) {
        if(!playerCards[P[i]]) {
            playerCards[P[i]] = [];
        }
        playerCards[P[i]].push(i);
    }

    // 초기 덱 상태 - 카드 번호와 위치가 일치
    let deck = Array.from({ length: N }, (_, i) => i);

    // 초기 덱 상태에서 올바르게 배치됐는지 확인
    if(isCorrectlyDistributed(deck)) {
        return 0;
    }

    // 현재 덱에서 카드가 올바르게 배치됐는지 확인
    function isCorrectlyDistributed(deck) {
        for(const [player, cards] of Object.entries(playerCards)) {
            for(const card of cards) {
                if(deck.indexOf(card) % 3 !== Number(player)) {
                    return false;
                }
            }
        }
        return true;
    }

    const visited = new Set([JSON.stringify(deck)]);
    let count = 0;

    while(1) {
        // 카드 섞기
        const newDeck = Array(N);
        for(let i = 0; i < N; i++) {
            newDeck[S[i]] = deck[i];
        }
        deck = newDeck;
        count++;

        // 올바르게 배치됐는지 확인
        if(isCorrectlyDistributed(deck)) {
            return count;
        }

        // 동일한 패턴 발생 시
        const deckStr = JSON.stringify(deck);
        if(visited.has(deckStr)) {
            return -1;
        }
        visited.add(deckStr);
    }

    return -1;
}