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

문제 요약

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

 

상자의 개수가 n일 때, 1부터 n까지의 숫자가 적혀있는 카드가 순서에 관계없이 n개의 상자에 하나씩 들어있다.
임의의 상자를 하나를 골랐을 때 나온 카드의 숫자가 8이면, 8번째 상자를 열어 카드를 확인한다.
이렇게 열어야 하는 상자가 이미 열려있을 때까지 이 과정을 반복한다.

이때 모든 상자가 열리면 0을 반환하고 그렇지 않다면 위 과정을 한번 더 실행한다.
과정이 끝나면 첫번째 과정에서 연 상자의 수와 두번째 과정에서 연 상자의 수를 곱한다.
이때 나올 수 있는 최대 점수를 구하는 문제이다.

 

접근

 

처음에는 문제가 너무 복잡하다고 생각했지만 예제를 직접 그려보면서 보니 사이클을 이루는 숫자 조합들을 찾고 크기가 가장 큰 두 그룹의 곱만 반환하면 된다는 게 보였다.

cards의 값을 check_box 함수를 통해 상자를 까보면서 visit에 v값으로 저장해주었다.
하나의 사이클이 끝나면 v+=1를 해주어 다른 그룹임을 표시했다.

 

v가 1이라면 check_box 함수가 한번만 실행된 것, 즉 한번에 모든 상자들이 열린 것이므로 0을 반환했고
그 외의 경우에 대해서는 각 사이클의 크기를 구해 가장 큰 값과 그 다음 큰 값을 곱해서 반환해주었다.

 

코드

def solution(cards):
    def check_box(num):
        nonlocal v

        if visit[num] == v:
            return

        if visit[num] == -1:
            visit[num] = v
            check_box(cards[num] - 1)

    visit = [-1] * len(cards)
    v = 0
    for card in cards:
        if visit[card - 1] == -1:
            check_box(card - 1)
            v += 1

    # 각 visit 그룹별로 가장 개수가 많은 2개 세기
    if v==1:
        return 0 

    cnt = [0] * v
    for vi in visit:
        cnt[vi] += 1

    cnt.sort(reverse=True)

    answer = cnt[0] * cnt[1]

    return answer