[Python] 프로그래머스 131130. 혼자 놀기의 달인 (Lv.2)

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

프로그래머스

 

기본적인 그래프 탐색이나 사이클에 대한 개념이 있으면 쉽게 풀 수 있는 문제입니다.

 

지문의 설명은 결국 상자와 카드를 기준으로 사이클이 생기면 회차 한 번이 종료된다는 얘기입니다. 사이클은 어느 곳에서 시작하던지 한바퀴가 돌게 되고, 이 문제의 경우 사이클은 정확히 원형으로 들어오기만 하는 노드가 존재하지 않습니다.

 

따라서 입력을 1번 순회하면서 사이클을 이루는 카드의 갯수들을 카운팅해 정답의 후보에 넣어주고, 최종적으로 그 중 가장 큰 값 두개를 뽑아 곱해주면 됩니다.

만약 사이클의 갯수가 하나라면, 즉 정답의 후보가 1개라서 곱할수가 없다면 0을 return 하면 됩니다.

 

예제 케이스를 바탕으로 설명해보겠습니다.

 

입력 cards로 [8,6,3,7,2,5,1,4]가 들어옵니다. 이 입력을 앞에서부터 체크하면서 사이클을 세어줄 겁니다.

 

1. 0번 위치가 가리키는 상자가 8(7번 위치)입니다. 0번 위치의 값을 0으로 체크해주고 다음 위치를 7번으로 기록합니다.

7번 위치가 가리키는 상자가 4(3번 위치)입니다. 7번 위치의 값을 0으로 체크해주고 다음 위치를 3번으로 기록합니다.

3번 위치가 가리키는 상자가 7(6번 위치)입니다. 3번 위치의 값을 0으로 체크해주고 다음 위치를 6번으로 기록합니다.

6번 위치가 가리키는 상자가 1(0번 위치)입니다. 6번 위치의 값을 0으로 체크해주고 다음 위치를 0번으로 기록합니다.

0번은 이미 0으로 체크된 상태이므로 첫 사이클을 종료합니다.

이 사이클의 노드 갯수는 4입니다. 4를 정답 후보 answer에 넣어줍니다. 이 때의 상태는 아래와 같습니다.

 

cards [0,6,3,0,2,5,0,0]   answer [4]

 

 

2. 1번 위치가 가리키는 상자가 6(5번 위치)입니다. 1번 위치의 값을 0으로 체크해주고 다음 위치를 5번으로 기록합니다.

5번 위치가 가리키는 상자가 5(4번 위치)입니다. 5번 위치의 값을 0으로 체크해주고 다음 위치를 4번으로 기록합니다.

4번 위치가 가리키는 상자가 2(1번 위치)입니다. 4번 위치의 값을 0으로 체크해주고 다음 위치를 1번으로 기록합니다.

1번은 이미 0으로 체크된 상태이므로 두번째 사이클을 종료합니다.

이 사이클의 노드 갯수는 3입니다. 3을 정답 후보 answer에 넣어줍니다. 이 때의 상태는 아래와 같습니다.

 

cards [0,0,3,0,0,0,0,0]   answer [4, 3]

 

 

3. 2번 위치가 가리키는 상자가 3(2번 위치)입니다. 2번 위치의 값을 0으로 체크해주고 다음 위치를 2번으로 기록합니다.

2번은 이미 0으로 체크된 상태이므로 세번째 사이클을 종료합니다.

이 사이클의 노드 갯수는 1입니다. 1을 정답 후보 answer에 넣어줍니다. 이 때의 상태는 아래와 같습니다.

 

cards [0,0,0,0,0,0,0,0]   answer [4, 3, 1]

 

더 이상 찾을 사이클이 존재하지 않습니다. 가능한 사이클 중에서 큰 값인 4와 3을 곱한 12를 return하면 됩니다.

 

def solution(cards):
    answer = []

    for i in range(len(cards)):
        if cards[i] == 0:
            continue
        box = cards[i] - 1
        count = 1
        cards[i] = 0

            while True:
                if cards[box] == 0:
                    answer.append(count)
                    break

                nbox = cards[box] - 1
                count += 1
                cards[box] = 0
                box = nbox

    answer.sort(reverse=True)

    return answer[0] * answer[1] if len(answer) > 1 else 0