Notion에서 작성한 글이라, 여기에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Challenger] 혼자 놀기의 달인

[혼자 놀기의 달인]

• 요새 구현, 시뮬레이션 문제들을 풀면서 정신이 오락가락한 상태였는데 간만에 상쾌하게 금방 풀었다.
• 36일차 챌린저 문제였던 도미노보다 먼저 출제됐다면 더 좋았을 것 같다.

접근 과정

• 문제를 읽어보면 사이클이 생각난다.
  • 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호를 붙인다. → 이 번호는 인덱스가 될 것임을 짐작할 수 있고, 1-indexed임에 주의해야 겠다.
    
  • 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인하고, 카드에 적힌 번호에 해당하는 상자를 여는 것을 반복, 열어야 하는 상자가 이미 열려있을 때까지 → $x, \sigma(x), \sigma(\sigma(x)), ...$ 사이클이구나!
    
  • 게임의 점수 = $\max($ 1번 상자 그룹에 속한 상자의 수 $\times$ 2번 상자 그룹에 속한 상자의 수 $)$
    • 사이클을 이루는 요소의 수의 최댓값과, 그 다음으로 큰 값을 곱해서 반환하면 되겠다.
• 사이클 카운팅은 쉽지만, 어떻게하면 더 효율적으로 셀 수 있을지 생각해 봤다.
  1. 사이클을 이루는 요소의 개수 리스트를 만들어 sort한 다음 두 개 선택해서 곱하기 : $O(n \lg n)$
  2. 최댓값, 그 다음으로 큰 값 정수형 변수 2개로 관리: $O(n)$

Solution. $O(n)$

def solution(cards):
    n = len(cards)
    used = set()
    first, second = 0, 0

    for i in range(n):
        if i not in used:
            j = i
            cur = 0
            while j not in used:
                cur += 1
                used.add(j)
                j = cards[j]-1
            if cur > first: first, second = cur, first
            elif cur > second: second = cur
            
    return first*second

---