혼자 놀기의 달인, python

문제 설명

문제 설명이 좀... 곤란했던 문제.

그냥 간단하게 말하자면 해당 배열 안에 있는 값들을 하나씩 따라가서 하나의 집합을 만들어 주는 것이다.

예를 들어서 [4, 3, 2, 1]라는 배열이 있다고 하자.

첫 번째 배열의 값에는 4가 들어 있다. 그러면 4의 위치에 있는 값을 찾으러 간다. 4의 위치에는 1이 있는데, 우리는 이미 앞에서 배열의 위치 1을 방문해줬다. 그러면 4와 1이 하나의 집합이 된다. 

그리고 두 번째 배열로 찾아간다. 두 번째 배열에는 3이 있다. 위치 3에 있는 배열로 가면 2가 있고 2는 이미 우리가 방문해준 위치다. 이렇게 원소가 2와 3인 배열이 하나 더 생긴다.

 

참고로 첫 번째 상자를 탐색했는데, 모든 원소가 첫 번째 집합에 들어있다면 정답은 0이다. 즉, 집합의 수가 0 혹은 1이면 0을 반환하라는 것이다. 나는 탐색의 마지막 부분 집합은 모두 0으로 해주라는 줄 알고 풀었다가 테스트 케이스 중 1, 3, 5가 줄줄 틀리면서 굉장히 당혹스러운... 상황을 맞이했다.

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

프로그래머스

 

문제 풀이

첫 번째 접근

처음에는 반복문으로 풀었다. 그러나 위에서 설명한 집합의 개수를 놓친 탓에 문제가 제대로 안 풀리는 상황을 맞이했다. 해당 부분만  고치면 맞았을 거 같지만, 그 당시에는 이게 문제인 줄 모르고 재귀를 이용하여 완전히 다른 풀이로 접근하였다.

두 번째 접근

반복문이 제대로 안 되자 이번에는 재귀를 이용했다.

일단 변수로는 cards, 연재 인덱스를 표시하는 num, 현재의 집합에 얼마나 많은 원소가 들어있는지를 판단하는 count가 있다.

그런데 현재 인덱스를 이미 방문하여 사이클이 생겼으면 정답 배열에 count를 넣은 후 반환한다.

만일 방문하지 않았다면 방문을 해주고 해당 위치에 있는 카드의 값(1을 빼줘야 인덱스 오류가 생기지 않는다)으로 다시 재귀를 실행한다.

 

그리고 0부터 카드의 범위까지 도는데, 만일 해당 인덱스를 방문하지 않았다면 재귀를 실행해준다.

 

후에 정답 배열이 2보다 작으면 0을 반환하고 그렇지 않으면 정렬을 해준 뒤 맨 뒤에 있는 것과 그 다음 뒤에 있는 것 두 개를 곱해준 값이 답이다(파이썬에서 일반 정렬은 오름차순이다).

 

코드

python

import copy

visit = [False for _ in range(101)]
answerList = []

def dfs(cards, num, count):
    if visit[num]:
        answerList.append(count)
        return
    visit[num] = True
    num = cards[num]
    num -= 1
    dfs(cards, num, count+1)
    

def solution(cards):
    answer = 0
    
    for i in range(len(cards)):
        if not visit[i]:
            dfs(cards, i, 0)
    
    if len(answerList) < 2:
        return 0
    answerList.sort()
    answer = answerList[len(answerList)-1] * answerList[len(answerList)-2]


    return answer