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

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

프로그래머스

 

✍️ 문제 요약

주어진 규칙에 따라 게임을 했을 때, 이 게임에서 얻을 수 있는 최고 점수를 구하라.

 

게임 규칙

- 정수 배열인 cards가 주어진다.

- cards의 각 숫자를 상자에 넣는다. (각 상자에는 1번부터 순차적으로 증가하는 번호를 붙인다.)

- 임의의 상자 하나를 선택하여 상자 안에 있는 숫자 카드를 확인한다.

    - 다음으로 확인한 숫자 카드에 적힌 번호에 해당하는 상자를 열어 안에 있는 숫자 카드를 확인한다.

    - 마찬가지로 숫자 카드에 적힌 번호에 해당하는 상자를 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복한다.

    - 여기까지 한 턴이 끝났다. 이렇게 연 상자들은 1번 그룹이다.

- 만약 1번 상자 그룹을 제외하고 남는 상자가 없으면 0점으로 게임이 종료된다.

- 그게 아니라면 다시 임의의 상자 하나를 선택하여 위 과정을 반복한다.

    - 이렇게 연 상자들은 2번 그룹이다.

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

 

💪 나의 풀이

주어진 cards로 나올 수 있는 모든 그룹을 미리 구해두자 ❗️

 

한 카드를 선택한 뒤 계속해서 적힌 수를 따라가며 그룹을 구성할건데, 이때 두 가지를 해야한다.

1. 그룹을 구성하고 있는 카드의 수를 1씩 증가한다. (cnt += 1)

2. 선택한 카드는 방문을 체크를 한다. (visited[i] = 1)

 

방문한 카드를 또 방문했을 때 하나의 그룹이 구성된 것이다.

이때, 그룹에 속한 카드(=상자)의 수인 cnt 변수를 별도의 리스트(boxes)에 담아둔다.

 

모든 cards를 방문했다면,

boxes 리스트를 내림차순 정렬하여 가장 큰 원소와 두 번째로 큰 원소의 곱인 boxes[0] * boxes[1]을 반환한다.

def solution(cards):
    n = len(cards)
    visited = [0] * n
    boxes = [] # 나올 수 있는 모든 그룹에 대해 구성하고 있는 박스 수를 저장해둘 리스트
    
    for i in range(n):
        cnt = 0
        while visited[i] == 0:
            visited[i] = 1 # 방문 처리
            idx = cards[i] - 1 # 다음에 열 카드
            i = idx # i 갱신
            cnt += 1 # 그룹을 구성하는 박스 수 1 증가
        if cnt != 0:
            boxes.append(cnt) # 그룹을 구성하는 박스 수 저장
           
    if len(boxes) < 2:
        return 0
    
    boxes.sort(reverse=True)
    
    return boxes[0] * boxes[1]

각 그룹을 구성하는 연산은, 모든 카드를 한 번씩 순회하므로 O(n)의 시간복잡도를 가진다.

boxes 리스트를 내림차순으로 정렬하는 연산은 O(n log n)의 시간 복잡도를 가진다.

 

따라서 전체 함수의 시간복잡도는 O(n log n)이며, 문제에서 cards의 최대 길이(=n)는 100이므로 양호하다.

 

🤔 다른 사람의 코드를 탐구해보기

def solution(cards):
    cards = [(x-1) for x in cards] # 인덱스로 맞추기
    groups = [] # 각 상자 그룹에 속한 카드 수
    visited = [0] * len(cards) # 각 카드들이 뽑힌 카드인지
    for x in cards:
        if visited[x]:
            continue
        tmp = [] # ✅ 한 턴에 뽑은 카드 그룹들 임시 저장
        while x not in tmp:
            tmp.append(x) # 카드 뽑음
            visited[x] = 1 # 방문 체크
            x = cards[x] # 다음에 뽑을 카드 갱신
        groups.append(len(tmp)) # 몇 개의 카드가 뽑혔는지 groups에 추가
        
    if len(groups) == 1:
        return 0
    
    groups.sort(reverse=True)
    return groups[0] * groups[1]

 

📚 참고 자료

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