[연습문제 / 프로그래머스] 131130번 : 혼자 놀기의 달인

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

 

스스로 푼 문제다!

 

문제 이해

처음엔 무슨 문제지 하면서 하나도 이해가지 않았다. 

예제를 기반으로 풀어보니 

- cards의 원소 - 1는 다음 인덱스의 값을 가리키고 있고,

- 0인덱스부터 시작하는데 인덱스 i에서 cards[i]로 이동한 다음,

- cards[i]를 방문하지 않았다면 cards[cards[i]]로 계속 이동하는 문제였다.

 

위와 같은 방식으로 계속 이동하다가 멈추었을 때가 하나의 박스 세트다. 각 갯수를 저장한 다음 가장 큰 값과 두번째로 큰 값의 곱을 반환하면 된다고 이해했다. 

 

풀이 이해

• cards의 값과 인덱스를 통일하기 위해서 전체 값에 -1을 한다. 
• 방문하지 않은 인덱스를 구별할 것이므로 visit를 초기화하고, 각 박스 세트의 박스 갯수를 세기위해 box_set도 초기화한다. 
• 인덱스 0부터 순차적으로 진행한는데, 방문하지 않은 인덱스 i에 대해 while문을 돌린다. 
  • index = cards[i]로 설정한뒤 visit[index] == 1이라면 while문을 break 하고
  • 아니라면 방문처리와 갯수를 증가하고 cards[index]로 이동한다.(index = cards[index])
• 갯수가 첫 번째로 많은 세트와 두번째로 많은 세트를 구해야하므로 내림차순으로 정렬한다. 
• 문제에서 세트가 한번에 끝나면 0을 반환하라고 했으므로 box_set가 하나만 있으면 0을 반환하고
• 아니라면 가장 큰 두 값의 곱을 반환한다. 

 

- 정답 풀이 :

def solution(cards):
    n = len(cards)
    for i in range(n):
        cards[i] -= 1
        
    box_set = []
    visit = [0] * n
    for i in range(n):
        if not visit[i]:
            visit[i], count, index = 1, 1, cards[i]
            while True:
                if visit[index]:
                    box_set.append(count)
                    break
                visit[index] = 1
                count += 1
                index = cards[index]            
    box_set.sort(reverse = True)
    
    if len(box_set) == 1:
        return 0
    else:
        return box_set[0] * box_set[1]