혼자 놀기의 달인 프로그래머스 - Python

 

프로그래머스

문제 이해가 잘 되지 않았던 문제다.

결론적으로 이 문제는 원소의 개수가 가장 큰 두 집합을 구하는 문제다.

cards에서 임의의 숫자를 선택하여 규칙대로 만들어진 1번째로 생긴그룹 2번째로 생긴 그룹의 원소 개수의 곱 중 최대값을 알아내야함.

어떤 수를 먼저 선택해도 규칙대로 하다보면 같은 집합의 형태가 나온다! 나만 그 집합의 순서가 다를 뿐, 그 중 1번 2번 그룹 원소 개수 곱의 최대값을 알아야하니, 제일 원소의 개수가 가장 큰 것 2가지를 구하면된다.

import collections

def solution(cards):
    leng = len(cards)
    unvisited = [True]*leng
    scores = collections.Counter()
    
    for i in range(leng):
        if unvisited[i] == True:
            scores[i] = 0
            pos = i
            while True:
                unvisited[pos] = False
                pos = cards[pos] - 1
                scores[i] += 1
                if unvisited[pos] == False:
                    break
    # 데이터의 개수가 많은 순으로 정렬된 배열을 리턴               
    answer = scores.most_common(2)
    
    if len(answer) == 1:
        return 0
    else:
        return (answer[0][1]*answer[1][1])
    
# 원소의 개수가 가장 큰 두 집합을 알아내는 문제

 

참고

프로그래머스 혼자 놀기의 달인