혼자 놀기의 달인(프로그래머스) 문제풀이

문제 

https://school.programmers.co.kr/learn/courses/30/lessons/131130

프로그래머스

 

 

 

문제 접근 방식

각 상자안에 숫자 카드가 존재하며 카드 번호에 해당하는 상자들을 열고, 만약 이미 열었던 상자라면 거기까지를 그룹으로 만든다. 이러한 과정을 반복해서 그룹1, 그룹2를 만들고 각 그룹들의 상자 개수를 곱한 값 중 최댓값을 구하는 문제이다. 모든 경우의 수를 구해서 그 중 그룹 1, 그룹 2의 결과값이 최대인 값을 출력해야하는 완전 탐색 문제이며 아래 처리과정을 통해 문제를 해결했다.

1. 모든 상자를 순회하여 그룹1의 첫번째 상자를 선택해본다
    2. 해당 상자를 선택했을 때 만들어지는 그룹 1의 값을 구하고, 해당 상자들을 방문처리한다
    3. 남은 상자를 순회한다
        3.1. 남은 상자 중 하나를 골라서 그룹 2를 만들고 개수를 구한다
        3.2. (그룹 1 개수) x (그룹 2 개수) 값을 구하고 최댓값으로 갱신한다
2.  (그룹 1 개수) x (그룹 2 개수)의 최댓값을 출력한다

 

 

코드

# 특정 상자 번호를 선택했을 때 만들어지는 그룹의 개수를 반환
def get_count(cards, not_visited, index):
    count = 0
    while True:
        if count >= len(cards) or index not in not_visited:
            break
        not_visited.remove(index)
        index = cards[index]
        count += 1
    
    return count


def solution(cards):
    cards.insert(0, 0)
    answer = 0
    
    for i in range(1, len(cards)): # 그룹 1의 첫 상자가 될 상자를 선택한다
        not_visited = set([i for i in range(1, len(cards))]) # 아직 선택하지 않은 상자들을 초기화한다
        group1 = get_count(cards, not_visited, i) # i 번 상자를 선택했을 때 만들어지는 그룹의 개수를 구한다
        
        if len(not_visited) == 0: # 첫번째 그룹을 만들고 남은 상자가 없다면 pass한다
            continue
        
        for j in list(not_visited): # 남은 상자 중 하나의 상자를 선택해서 그룹 2의 개수를 구한다
            group2 = get_count(cards, not_visited, j)
            answer = max(answer, group1 * group2) # 최댓값으로 갱신한다
    
    return answer