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

문제 설명

혼자서도 잘 노는 범희는 어느 날 방구석에 있는 숫자 카드 더미를 보더니 혼자 할 수 있는 재미있는 게임을 생각해냈습니다.

숫자 카드 더미에는 카드가 총 100장 있으며, 각 카드에는 1부터 100까지 숫자가 하나씩 적혀있습니다. 2 이상 100 이하의 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드들을 준비하고, 준비한 카드의 수만큼 작은 상자를 준비하면 게임을 시작할 수 있으며 게임 방법은 다음과 같습니다.

준비된 상자에 카드를 한 장씩 넣고, 상자를 무작위로 섞어 일렬로 나열합니다. 상자가 일렬로 나열되면 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호를 붙입니다.

그 다음 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인합니다. 다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자를 확인합니다. 마찬가지로 숫자에 해당하는 번호를 가진 상자를 계속해서 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복합니다.

이렇게 연 상자들은 1번 상자 그룹입니다. 이제 1번 상자 그룹을 다른 상자들과 섞이지 않도록 따로 둡니다. 만약 1번 상자 그룹을 제외하고 남는 상자가 없으면 그대로 게임이 종료되며, 이때 획득하는 점수는 0점입니다.

그렇지 않다면 남은 상자 중 다시 임의의 상자 하나를 골라 같은 방식으로 이미 열려있는 상자를 만날 때까지 상자를 엽니다. 이렇게 연 상자들은 2번 상자 그룹입니다.

1번 상자 그룹에 속한 상자의 수와 2번 상자 그룹에 속한 상자의 수를 곱한 값이 게임의 점수입니다.

상자 안에 들어있는 카드 번호가 순서대로 담긴 배열 cards가 매개변수로 주어질 때, 범희가 이 게임에서 얻을 수 있는 최고 점수를 구해서 return 하도록 solution 함수를 완성해주세요.

제한사항

• 2 ≤ cards의 길이 ≤ 100
• cards의 원소는 cards의 길이 이하인 임의의 자연수입니다.
• cards에는 중복되는 원소가 존재하지 않습니다.
• cards[i]는 i + 1번 상자에 담긴 카드에 적힌 숫자를 의미합니다.

입출력 예

cards	result
[8,6,3,7,2,5,1,4]	12

입출력 예 설명

1, 4, 7, 8이 속하는 상자의 그룹과 2, 5, 6이 속하는 상자의 그룹과 3이 속하는 상자의 그룹이 존재합니다. 따라서 3번 상자를 고르지 않았을 때, 두 번의 시행에서 3과 4를 기록하며 최고 점수 12를 얻을 수 있습니다.

풀이

• 역대급 설명이 이상한 문제 중 하나... ㅡ.ㅡ?
• 설명대로 최소 케이스로 해보자.
  • 2카드를 뽑았다.
  • 그럼 카드는 [1, 2], 상자는 2개
  • 섞어봤자 [1, 2], [2,1]
  • 번호는 1, 2붙이면 되고...
  • 그 다음 임의의 상자를 하나 선택하면 [1]아니면 [2]
    • 그리고 [1]이면 [1]번 상자를 또 열어야 되는데 불가능
    • [2]도 마찬가지. 끝.
  • 그럼 [1]번 열었던 그룹이 1번 상자 그룹.
  • [2]는 2번 상자 그룹.
  • 이렇게 섞이지 않도록 따로 둔다.
    • 남은 상자가 없으면 게임 종료.
    • 근데 1번 상자 그룹만 있으면 획득 점수는 0점.
  • 그래서 1번 상자 그룹에 속한 상자 수와 2번 상자 그룹에 속상 상자의 수를 곱한 값이 게임의 점수.
    • 이런 게임에서 얻을 수 있는 최고 점수를 구하시오.
  • 근데 상자 안에 들어있는 카드 번호 순서대로 담긴 배열이 cards.
    • 카드 번호 순서대로가 의미가 있나? 무작위로 섞어서 나열하라며?
    • 아... 무작위로 섞여서 나열된 순서가 cards인가?
  • 근데 그 다음에 또 임이의 상자를 선택하라며?
• 뭐지?? (ㅡ.ㅡ) 구냥 다시 해보자...
  • 입출력 예에서 말하는 [8,6,3,7,2,5,1,4]가, 상자 안에 들어있는 카드의 순서이고.
    • [8],[6],[3],[7],[2],[5],[1],[4] 이렇게 8개의 상자가 있고,
    • 이중에 하나를 무작위로 선택하면
      • 8 -> 4 -> 7 -> 1 -> 8
      • 6 -> 5 -> 2 -> 6 -> 5 ...
      • 3 -> 3...
      • 7 -> 1 -> 8 ...
      • 2 -> 6 -> 5...
      • 5 -> 2 -> 6...
      • 1 -> 8...
      • 4 -> 7...
    • 아.........  visted 처리를 해야하는구나?
  • 알았다.
• 무지성 코딩 가즈아!

import collections

def solution(cards):
    len_cards = len(cards)
    unvisited = [True] * len_cards
    scores = collections.Counter()
    for i in range(len_cards):
        if unvisited[i] == True:
            scores[i] = 0
            pos = i
            while True:
                unvisited[pos] = False
                pos = cards[pos] -1
                scores[i] += 1
                print(unvisited, scores, cards, pos)
                if unvisited[pos] == False:
                    break
    answer = scores.most_common(2)
    answer = answer[0][1] * answer[1][1]
    return answer
    
테스트 1
입력값 〉	[8, 6, 3, 7, 2, 5, 1, 4]
기댓값 〉	12
실행 결과 〉	테스트를 통과하였습니다.
출력 〉	[False, True, True, True, True, True, True, True] Counter({0: 1}) [8, 6, 3, 7, 2, 5, 1, 4] 7
[False, True, True, True, True, True, True, False] Counter({0: 2}) [8, 6, 3, 7, 2, 5, 1, 4] 3
[False, True, True, False, True, True, True, False] Counter({0: 3}) [8, 6, 3, 7, 2, 5, 1, 4] 6
[False, True, True, False, True, True, False, False] Counter({0: 4}) [8, 6, 3, 7, 2, 5, 1, 4] 0
[False, False, True, False, True, True, False, False] Counter({0: 4, 1: 1}) [8, 6, 3, 7, 2, 5, 1, 4] 5
[False, False, True, False, True, False, False, False] Counter({0: 4, 1: 2}) [8, 6, 3, 7, 2, 5, 1, 4] 4
[False, False, True, False, False, False, False, False] Counter({0: 4, 1: 3}) [8, 6, 3, 7, 2, 5, 1, 4] 1
[False, False, False, False, False, False, False, False] Counter({0: 4, 1: 3, 2: 1}) [8, 6, 3, 7, 2, 5, 1, 4] 2

• 제출!
  • 왓? 테스트 케이스 2 실패...

정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	실패 (런타임 에러)
테스트 3 〉	통과 (0.04ms, 10.2MB)
테스트 4 〉	통과 (0.07ms, 10.2MB)
테스트 5 〉	통과 (0.03ms, 10.2MB)
테스트 6 〉	통과 (0.06ms, 10.1MB)
테스트 7 〉	통과 (0.05ms, 10.1MB)
테스트 8 〉	통과 (0.08ms, 10.2MB)
테스트 9 〉	통과 (0.05ms, 10.3MB)
테스트 10 〉	통과 (0.05ms, 10.1MB)

• 아.... 아까 문제 읽을 때 체크해놓고 코딩을 안했다.
• 상자그룹이 하나일 때는 0이다.

import collections

def solution(cards):
    len_cards = len(cards)
    unvisited = [True] * len_cards
    scores = collections.Counter()
    for i in range(len_cards):
        if unvisited[i] == True:
            scores[i] = 0
            pos = i
            while True:
                unvisited[pos] = False
                pos = cards[pos] -1
                scores[i] += 1
                if unvisited[pos] == False:
                    break
    answer = scores.most_common(2)
    if len(answer) == 1:
        return 0
    else:
        return (answer[0][1] * answer[1][1])
        
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.06ms, 10.2MB)
테스트 3 〉	통과 (0.06ms, 10.3MB)
테스트 4 〉	통과 (0.05ms, 10.3MB)
테스트 5 〉	통과 (0.03ms, 10.2MB)
테스트 6 〉	통과 (0.06ms, 10.1MB)
테스트 7 〉	통과 (0.05ms, 10.2MB)
테스트 8 〉	통과 (0.06ms, 10.2MB)
테스트 9 〉	통과 (0.05ms, 10.2MB)
테스트 10 〉	통과 (0.09ms, 10.2MB)

• 고수의 풀이.
  • 그냥 리스트로 풀어도 되는 거였나?
  • 속도가 빠르지 않다.

def solution(cards):
    answer = []
    for i in range(len(cards)):
        tmp = []
        while cards[i] not in tmp:
            tmp.append(cards[i])
            i = cards[i] - 1
        answer.append([] if sorted(tmp) in answer else sorted(tmp))
    answer.sort(key=len)

    return len(answer[-1]) * len(answer[-2])
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (7.19ms, 10.1MB)
테스트 3 〉	통과 (2.24ms, 10.3MB)
테스트 4 〉	통과 (0.16ms, 10.2MB)
테스트 5 〉	통과 (0.15ms, 10.1MB)
테스트 6 〉	통과 (0.61ms, 10.1MB)
테스트 7 〉	통과 (0.14ms, 10.1MB)
테스트 8 〉	통과 (0.23ms, 10.1MB)
테스트 9 〉	통과 (0.16ms, 10.1MB)
테스트 10 〉	통과 (0.19ms, 10.3MB)

• 디큐를 쓴게 빠르네.
  • 정렬을 하지 않아도 되고...
  • 딕셔너리 보단 디큐가 더 빠른...

import heapq
def solution(cards):
    answer = 1
    alist = []
    visit = [0]*len(cards)
    for i in range(len(cards)):
        cnt = 0
        a = cards[i]-1
        while True:
            if visit[a] == 1:
                break
            else:
                visit[a] = 1
                a = cards[a]-1
                cnt += 1
        heapq.heappush(alist,-cnt)

    a = heapq.heappop(alist)
    b = heapq.heappop(alist)
    answer = a*b

    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.03ms, 10.2MB)
테스트 3 〉	통과 (0.03ms, 10.2MB)
테스트 4 〉	통과 (0.05ms, 10.3MB)
테스트 5 〉	통과 (0.02ms, 10.3MB)
테스트 6 〉	통과 (0.02ms, 10.1MB)
테스트 7 〉	통과 (0.03ms, 10.2MB)
테스트 8 〉	통과 (0.03ms, 10.2MB)
테스트 9 〉	통과 (0.06ms, 10.1MB)
테스트 10 〉	통과 (0.04ms, 10.1MB)

• 혹시나 해서 while sum( ) > 0: 으로 바꾸어보았는데 별로?

import collections

def solution(cards):
    len_cards = len(cards)
    unvisited = [True] * len_cards
    scores = collections.Counter()
    while sum(unvisited) > 0:
        i = unvisited.index(True)
        scores[i] = 0
        pos = i
        while True:
            unvisited[pos] = False
            pos = cards[pos] -1
            scores[i] += 1
            if unvisited[pos] == False:
                break
    answer = scores.most_common(2)
    if len(answer) == 1:
        return 0
    else:
        return (answer[0][1] * answer[1][1])
        
정확성  테스트
테스트 1 〉	통과 (0.02ms, 9.99MB)
테스트 2 〉	통과 (0.04ms, 10.2MB)
테스트 3 〉	통과 (0.04ms, 10.2MB)
테스트 4 〉	통과 (0.06ms, 10.3MB)
테스트 5 〉	통과 (0.03ms, 10.2MB)
테스트 6 〉	통과 (0.03ms, 10.2MB)
테스트 7 〉	통과 (0.11ms, 10.2MB)
테스트 8 〉	통과 (0.14ms, 10.2MB)
테스트 9 〉	통과 (0.10ms, 10.2MB)
테스트 10 〉	통과 (0.08ms, 10.3MB)