티스토리 뷰

반응형
프로그래머스 혼자 놀기의 달인 Python 풀이

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


문제

문제

1부터 N까지 번호가 붙은 상자가 있고, 각 상자 안에는 다음에 열 상자의 번호가 적힌 카드가 들어 있습니다.

임의의 상자를 하나 선택해 그 안의 숫자를 확인하고, 그 숫자에 해당하는 상자를 차례로 열어 나갑니다.

이미 열어본 상자를 다시 만나면 첫 번째 그룹이 완성됩니다.

이후 첫 번째 그룹을 제외한 상자들 중 하나를 다시 선택하여 같은 과정을 반복하면 두 번째 그룹이 완성됩니다.

게임의 점수는 첫 번째 그룹의 상자 개수 × 두 번째 그룹의 상자 개수이며, 가능한 조합 중 가장 큰 값을 구하는 문제입니다.


입력 출력
[8,6,3,7,2,5,1,4] 12

문제작동원리

  1. 각 상자에는 “다음에 열 상자 번호”가 적힌 카드가 들어 있습니다.
  2. 하나의 상자에서 시작하면, 그 안의 숫자가 다음 상자의 인덱스를 가리키는 연쇄 구조(사이클)를 만듭니다.
  3. 이미 방문한 상자를 만나면 하나의 그룹(사이클)이 형성됩니다.
  4. 전체 상자에는 여러 개의 독립적인 사이클이 존재하며,
    그중 두 개의 사이클 크기를 곱했을 때 가장 큰 값을 찾는 것이 목표입니다.
  5. 예를 들어 [8,6,3,7,2,5,1,4]에서는
    • 1→8→4→7→1 로 연결된 그룹 (크기 4)
    • 2→6→5→2 로 연결된 그룹 (크기 3)
    • 3→3 로 연결된 그룹 (크기 1)

    따라서 두 그룹(4와 3)을 선택해 4×3=12가 최대 점수입니다.



아이디어

  • 상자-카드 구조는 그래프의 사이클 탐색으로 볼 수 있습니다.
  • 각 상자 번호를 정점으로, 카드의 숫자를 간선으로 연결하면 전체가 하나 이상의 사이클 집합이 됩니다.
  • 모든 상자를 순회하며 방문하지 않은 상자부터 탐색해 사이클의 크기를 구합니다.
  • 각 사이클의 크기를 리스트에 저장하고, 내림차순 정렬 후 상위 두 개를 곱한 값을 반환합니다.


전체코드

def solution(cards):
    N=len(cards)
    total_max=0
    for i in range(N):
        check = [0 for _ in range(N)]
        start=cards[i]
        check[i]=1
        cnt_temp=1
        while True:
            if check[start-1]==0:
                check[start-1]=1
                start=cards[start-1]
                cnt_temp+=1
            else:
                break

        for j in range(N):
            if check[j]!=0:
                continue
            else:
                start=cards[j]
                cnt_temp2 = 1
                check[j]=1
                check2=check[:]
                while True:
                    if check2[start - 1] == 0:
                        check2[start - 1] = 1
                        start = cards[start - 1]
                        cnt_temp2 += 1
                    else:
                        break
            if total_max


결론

이 문제는 순열 구조에서 두 개의 사이클 크기 곱의 최댓값을 찾는 문제입니다.

각 상자는 다음 상자를 가리키는 방향 그래프 형태이므로, 모든 상자에 대해 사이클 탐색을 수행해야 합니다.

사이클의 크기를 구한 뒤, 그중 두 개를 선택하여 곱했을 때 최대값을 구하면 됩니다.

결과적으로 [8,6,3,7,2,5,1,4]의 입력에서는 정답이 12가 됩니다.


반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2025/10   »
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함
반응형