99클럽 코테 스터디 38일차 TIL [Greedy]

- 오늘의 학습 키워드 : 탐욕법(Greedy)

[문제 이름 : 혼자 놀기의 달인 (프로그래머스 131130, Lv 2)]

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

 

문제 설명
혼자서도 잘 노는 범희는 어느 날 방구석에 있는 숫자 카드 더미를 보더니 혼자 할 수 있는 재미있는 게임을 생각해냈습니다.
숫자 카드 더미에는 카드가 총 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~100이하 자연수를 하나 정해 그 수보다 작거나 같은 숫자 카드 준비
// 준비한 카드 수만큼 작은 상자 준비
// 준비된 상자에 카드 한 장 넣고, 무작위로 일렬로 나열. 상자가 나열된 순서에 따라 1번부터 순차적으로 증가하는 번호 붙임
// 임의의 상자 선택 후 카드 확인 -> 이 번호에 해당하는 상자를 열어 숫자 확인, 반복하며 열어야 하는 상자가 이미 열릴 때까지 반복
// 이렇게 연 상자가 1번 그룹, 다른 상자와 섞이지 않게 둠. 1번 상자 그룹 제외하고 남는 상자 없으면 게임 종료, 이때 획득 점수는 0점
// 그렇지 않다면 남은 상자 중 다시 임의의 상자 하나를 골라 같은 방식으로 이미 열려있는 상자 만날 때까지 상자를 엶. 이는 2번 상자 그룹
// 1번 상자 그룹의 상자 수 * 2번 상자 그룹의 상자 수 = 게임의 점수
// cards: 상자 안에 들어있는 카드 번호가 순서대로 담긴 배열
// 이 게임에서 얻을 수 있는 최고 점수 return

import java.util.*;

class Solution {
    public int solution(int[] cards) {
        int cardLen = cards.length;
        boolean[] visited = new boolean[cardLen];
        List<Integer> groupList = new ArrayList<>();
        
        // 무작위니까 cards배열 순회하면서 각 결과값 출력
        for(int i=0; i<cardLen; i++) {
            if(!visited[i]) {
                int size = 0;
                int now = i;
                
                while(!visited[now]) {
                    visited[now] = true;
                    now = cards[now] - 1;
                    size++;
                }
                
                groupList.add(size);
            }
        }
        
        if(groupList.size() < 2) {
            return 0;
        } else {
            Collections.sort(groupList);
            int answer = groupList.get(groupList.size() - 1) * groupList.get(groupList.size() - 2);
            return answer;
        }
    }
}

 

[풀이 과정]

1. 임의의 상자를 하나 선택하여 상자 그룹을 만드므로, for문에서 각 인덱스부터 시작해서 그룹을 만들어본다.

2. 1번 과정을 통해 만든 그룹의 크기를 groupList라는 ArrayList를 생성해서, 이에 저장한다.

3. 두 상자 그룹의 상자 수를 곱한 값이 최대 값이 되어야 하므로, groupList를 크기 순으로 정렬한다.

4. 1개 이하라면 0을 리턴하고, 2개 이상인 경우에는 제일 마지막 두 개의 값을 곱한 값을 리턴한다.

 

풀이 시간 : 30분

 

다른 풀이 방법을 찾아보았다.

1. DFS로 메서드를 나눠서 구현하는 방법

(1) 크기 순으로 자동 정렬되도록 PriorityQueue를 이용한다.

(2) DFS를 구현하여 배열의 사이즈를 측정한다.

(3) 다음 과정은 위 풀이와 동일하다.

import java.util.*;

class Solution {
    static PriorityQueue<Integer> queue;
    public int solution(int[] cards) {
        int answer = 0;
        int cardLen = cards.length;
        boolean[] visited = new boolean[cardLen];
        
        queue = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int i=0; i<cardLen; i++) {
            if(!visited[i]) {
                dfs(cards, i, visited, 0);
            }
        }
        
        if(queue.size() >= 2) {
            answer = queue.poll() * queue.poll();
        }
        
        return answer;
    }
    
    private void dfs(int[] cards, int num, boolean[] visited, int count) {
        // 이미 읽었던 상자라면
        if(visited[num]) {
            queue.add(count);
            return ;
        }
        
        visited[num] = true;
        dfs(cards, cards[num]-1, visited, count+1);
    }
}

 

2. 유니온 파인드를 이용하는 방법

1. 유니온 파인드 알고리즘 사용을 위해, parents 배열을 생성하고, 값을 인덱스와 동일하게 초기화한다.
2. cards 배열의 값에 -1을 해주어 배열의 인덱스 숫자와 카드 숫자를 동일하게 맞춘다.

3. 상자를 start, 상자 안의 카드 숫자를 end로 지정한다. start와 end가 가리키는 상자가 같은 집합이 아닌 경우(parents값이 다른 경우), union 연산을 통해 같은 집합으로 만든다. (parents값을 같도록 저장한다.)

4. start와 end가 가리키는 상자가 같은 집합이 아닐 경우, 반복해서 같은 집합으로 만든다.

import java.util.*;

class Solution {
    int[] parents;
    public int solution(int[] cards) {
        parents = new int[cards.length];
        for(int i=0; i<parents.length; i++) {
            parents[i] = i;
        }
     
        for(int i=0; i<cards.length; i++) {
            cards[i] -= 1;
        }
        
        for(int i=0; i<cards.length; i++) {
            int start = i;
            int end = cards[i];
            
            while(parents[start] != parents[end]) {
                union(start, end);
                
                start = end;
                end = cards[end];
            }
        }
        
        Integer[] count = new Integer[cards.length];
        Arrays.fill(count, 0);

        for(int i=0; i< cards.length; i++) {
            int key = parents[i];
            if(count[key] > 0) {
                continue;
            }
            
            for(int j=0; j<parents.length; j++) {
                if(key == parents[j]) {
                    count[key]++;
                }
            }
        }
        
        Arrays.sort(count, Collections.reverseOrder());
        return count[0] * count[1];
    }
    
    private void union(int a, int b) {
        a = find(a);
        b = find(b);
        
        if(a != b) {
            parents[b] = a;
        }
    }
    
    private int find(int a) {
        if(a == parents[a]) return a;
        else return parents[a] = find(parents[a]);
    }
}