99클럽 코테 스터디 38일차 TIL, 프로그래머스 / 혼자 놀기의 달인

🔑 오늘의 학습 키워드

🔗 문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/131130

 

def solution(cards):
    opened = [False] * len(cards)
    box_group = []
    
    def open_box(cards, idx):
        opened[idx] = True
        tmp = [idx]    
        while True:
            next_open = cards[idx] - 1
            if opened[next_open]:
                break
            opened[next_open] = True
            idx = next_open
            tmp.append(idx)
        box_group.append(len(tmp))
        
    for i in range (len(cards)):
        if opened[i]:
            continue
        open_box(cards,i)
    
    box_group.sort(reverse = True)
    if len(box_group) == 1:
        return 0
    return box_group[0] * box_group[1]

 

🗒️ 공부한 내용 본인의 언어로 정리하기

🤔 문제를 보고 든 생각

주어진 카드 뭉치를 열었을 때 해당 인덱스에 맞는 박스를 열어가면서 실행하면 되겠구나

 

그러면 박스를 열었는지 확인하는 배열이랑, 만든 그룹 리스트의 길이를 저장해 나간뒤 길이가 가장 큰 2개를 곱하면 되겠다.

 

⏰ 예상 시간 복잡도 O(N)

제한 사항

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

 

✅ 오늘의 회고

- 쉽다 그리디 :)

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL