문제 링크

문제 풀이 아이디어

1번 상자 그룹, 2번 상자 그룹?

문제의 설명을 읽어보면 혼자 노는 방법이 자세히 적혀있습니다. 게임은 총 2번의 시도로 나뉘어지고 각각의 시도를 통해서 얻은 상자의 갯수를 곱해서 구하는 것으로 되어있습니다. 이 방법에 따라서 랜덤으로 상자를 선택하는 경우에 따라 각각의 얻을 수 있는 점수의 경우의 수를 모두 확인하고 그 중에 최댓값을 골라야 할까요?

게임의 원리를 알면 우리는 이 혼자 노는 방법을 코드로 구현할 필요가 없습니다. cards 배열이 주어지면 이미 상자의 그룹은 정해져있는 상태입니다. 따라서 혼자 노는 방법과 상관없이 어떤 상자들이 그룹을 이루는지 더 단순하게 말하면 그룹에 속한 상자의 갯수만 구하면 됩니다.

문제에서 주어진 예시로 설명을 하면 상자는 [1, 4, 7, 8] / [2, 5, 6] / [3]의 3개의 그룹으로 나뉩니다. 각각의 그룹에 어떤 상자를 랜덤으로 뽑든지 간에 무조건 같은 그룹의 상자를 모두 열고 끝나게 됩니다.

따라서 우리가 할 일을 상자를 그룹으로 나누는 일입니다.

그룹 나누기

모든 상자를 순회하면서 열어 봅니다. 어떤 상자부터 시작하는지 관계없으므로 1번 상자부터 시작합니다. 1번 상자에서 나온 숫자의 상자를 열고, 다시 그 상자에서 나온 숫자를 여는 것을 반복해서 상자에서 나온 숫자의 상자가 이미 열린 경우까지 반복합니다.

1번 상자가 속한 그룹이 끝나면 2번 상자에서 다시 시작합니다. 만약 2번 상자가 1번 상자와 같은 그룹에 있었다면 이미 열린 상태입니다. 그런 경우 3번 상자로 넘어가면 됩니다. 이렇게 모든 상자가 열릴 때까지 1번 ~ n번 상자까지 반복합니다.

그룹으로 나뉘었다면 최대로 얻을 수 있는 점수는 그룹 크기가 가장 큰 두 그룹의 count를 곱하면 됩니다.

O(1)

위 동작을 위해서는 계속해서 어떤 상자가 열렸는지 안 열렸는지 확인해야 합니다. 이렇게 반복되는 동작은 최대한 시간복잡도를 낮게 설계해야 합니다. 여러 방법이 있지만 저는 Set을 사용했습니다.

코드

func solution(_ cards:[Int]) -> Int {
    
    // 이미 열린 상자를 담는 집합
    var opened = Set<Int>()
    
    // 그룹의 길이를 넣어두는 배열
    var group = [Int]()
    
    // 모든 상자를 순회
    for i in 0..<cards.count {
        // 이미 열린 상자면 continue
        if opened.contains(i) { continue }
        
        // 같은 그룹에 있는 상자 열기
        var now = i
        var count = 0
        // 이미 열린 상자에 숫자가 도달할 때까지 상자 열기
        while !opened.contains(now) {
            // 열린 상자 집합에 넣고
            opened.insert(now)
            
            // 그룹 길이에 1추가
            count += 1
            // 다음 상자
            now = cards[now] - 1
        }
        
        // 한 그룹에 속하는 모든 상자를 찾은 경우 그룹 길이에 push
        group.append(count)
    }
    
    // 비내림차순으로 정렬
    let sorted = group.sorted(by: >)
    
    // group의 길이가 1인 경우 (= 1단계에서 게임이 끝나는 경우) 예외처리
    return sorted.count > 1 ? sorted[0] * sorted[1] : 0
}