프로그래머스 탐욕법

문제

풀이

import java.util.*;

class Solution {
    public int solution(int n, int[] lost, int[] reverse) {
        int answer = n - lost.length;
            
        Arrays.sort(lost);
        Arrays.sort(reverse);
            
        // 여벌이 있는 학생이 체육복을 도난 당한 경우
        for(int i = 0; i < lost.length; i++) {
            for(int j = 0; j < reverse.length; j++) {
                if(lost[i] == reverse[j]) { // 자기 자신일 경우
                    answer++; // 여벌의 자기 옷 입으면 되므로 참여자 수 증가
                    lost[i] = -1;
                    reverse[j] = -1;
                    break;
                }
            }
        }
        
        // 다른 사람에게 체육복을 빌려주는 경우
        for(int i = 0; i < lost.length; i++) {
            for(int j = 0; j < reverse.length; j++) {
                // 도난당한 사람보다 1 작거나 1 큰경우만 가능
                if((lost[i] - 1 == reverse[j]) || (lost[i] + 1 == reverse[j])) {
                    answer++;
                    reverse[j] = -1;
                    break;
                }
            }
        }
            
        return answer;
    }
}

결과

문제

풀이

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        int min = 0;
        
        for(int max = people.length - 1; min <= max; max--) {
            if(people[min] + people[max] <= limit) {
                min++;
            }
            answer++;
        }
        
        return answer;
    }
}

결과

문제

풀이

import java.util.*;

class Solution {
    public int solution(int n, int[][] costs) {
        int answer = 0;
        int[] parent = new int[n];
        
        for(int i = 0; i < parent.length; i++) {
            parent[i] = i;
        } 
        Arrays.sort(costs, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2] - o2[2]; // 비용을 기준으로 오름차순 정렬
            }
        });
        
        for (int i = 0; i < costs.length; i++) {
            // 사이클 판독
            if(find(parent, costs[i][0]) != find(parent, costs[i][1])) {
                answer += costs[i][2];
                union(parent, costs[i][0], costs[i][1]);
            }
        }
        return answer;
    }
    public int find(int[] parent, int node) {
        if(parent[node] == node)
            return node;
        return find(parent, parent[node]);
    }
    public void union(int[] parent, int node1, int node2) {
        int p1 = find(parent, node1);
        int p2 = find(parent, node2);
        
        if (p1 < p2) parent[p2] = p1;
        else parent[p1] = p2;
    } 
}

크루스칼 알고리즘을 이용하면 된다.

결과