[PS, Algorithm] - 혼자 놀기의 달인 (프로그래머스 연습문제, LEVEL 2)

📒문제

📌풀이

def solution(cards):
    def game(cur):
        result = 0
        visit = [False for i in range(len(cards))]
        data = []
        
        while visit[cur] != True:
            result += 1
            data.append(cur)
            visit[cur] = True        
            cur = cards[cur]-1
        
        return tuple(data), result
    
    d = []
    for i in range(len(cards)):
        key, val = game(i)
        d.append((key, val))
    d.sort(key = lambda x: x[1], reverse = True)
    
    if d[0][1] == len(cards): return 0
    
    result = -1
    for i in range(len(cards)):
        for j in range(i+1, len(cards)):
            if len(set(d[i][0])&set(d[j][0])) == 0:
                if d[i][1] * d[j][1] > result: result =  d[i][1] * d[j][1]
    
    return result

문제를 푸는 것보다 문제를 이해하는게 더 힘든 문제였던 것 같다.

문제를 다시 설명해보자면

cards가 [8, 6, 3, 7, 2, 5, 1, 4]고, 임의로 맨 처음 숫자인 8을 뽑았다면,

• 그 뒤에는 cards[8-1] = 4로 이동(문제에서 시작점을 1로 줌)
• 그 뒤에는 cards[4-1] = 7로 이동
• 그 뒤에는 cards[7-1] = 1로 이동
• 그 뒤에는 cards[1-1] = 8인데, 8은 이미 방문했으므로 1번 상자 그룹 종료

이런 식으로 해서 그룹에 가장 많은 카드를 넣는 경우의 수를 서로 곱하는 문제다.

애초에 cards 의 최대 길이가 100밖에 안되기 때문에 굳이 시간 복잡도를 고민할 필요 없이 모든 점을 시작점으로 놓고 그룹을 만드는 수를 각각 구한다음 추후 뽑은 카드가 다른 카드와 겹치진 않는지만 확인해주면 된다고 생각했다.