프로그래머스 [Lv. 2] 혼자 놀기의 달인 {언어 : Python}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/131130?language=python3

프로그래머스

정답 코드

def solution(cards):
    n = len(cards)
    v = [0 for _ in range(n+1)]
    
    stack = []
    
    def dfs(s, cnt):
        nextC = cards[s-1]
        if v[nextC]:
            stack.append(cnt)
            return
        v[nextC] = 1
        dfs(nextC, cnt+1)
    
    for card in cards:
        if v[card]:
            continue
        v[card] = 1
        dfs(card, 1)
    
    answer = 0
    if len(stack) >= 2:
        stack.sort()
        answer = stack[-1] * stack[-2]
        
    return answer

풀이 방법

1. 첫 번째 카드부터 dfs를 사용해서 순회를 한다.
2. 상자가 열려 있는지 visited 배열을 통해 확인한다.
3. 열려 있으면 dfs를 종료하고 stack에 획득한 카드의 수 cnt 값을 저장한다.
4. stack의 개수가 2개 이상인 경우만 곱셈이 가능하다.
   1. 정렬을 해서 개수가 많은 상자 두 개를 곱한 뒤 answer에 치환한다.
5. answer를 return 한다.

느낀점

• cards 배열을 직접 무작위로 섞어야 하는 줄 알았는데 다행히 무작위로 섞은 배열을 input 값으로 준다.
• 따라서 나는 상자의 개수만 파악하면 되는 간단한 문제였다.