[PCCP] 스택 · 큐 · 정렬 · 그리디 알고리즘 [10]

▼ Why ?

이번 문제는 전에 배웠던 해시함수와 정렬을 활용하여 해결하는 문제이기 때문에 한 번 풀어보았다.

---

▼ 과일 장수

 

문제 정보

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
• 1 ≤ tangerine의 원소 ≤ 10,000,000

 

입출력 예

 

어떻게 해결해야 할까 ?

1. 일단 상자에 담은 귤의 종류의 수를 최소화시켜야 하기 때문에, 귤 종류를 key값으로 하고 해당 종류의 귤의 개수를 value값으로 하는 HashMap 객체를 하나 생성하 'getOrDefault()' 메서드를 이용하여 데이터를 저장해주자
2. 이 HashMap 객체를 활용해서 'keySet' 메서드로 key값들을 컬렉션 객체에 저장해주고, 해당 컬렉션 객체를 가장 큰 value값을 갖고 있는 key값부터 value값을 기준으로 내림차순 정렬해준다
3. 상자에 담을 개수만큼 해당 컬렉션 객체에서 꺼내주면 귤의 종류의 수의 최솟값을 구할 수 있다
4. 이처럼 데이터를 저장하고 탐색하는 용도로 컬렉션을 이용할 것이기 때문에 List를 구현한 class 중 ArrayList가 적합하다

 

해결 코드 0

• 'if(k <= 0) break;'의 위치가 중요하다

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
    
        HashMap<Integer, Integer> typeCount = new HashMap<>();
        for(int t : tangerine)
            typeCount.put(t, typeCount.getOrDefault(t, 0) + 1);
        
        ArrayList<Integer> typesSortedList = new ArrayList<>(typeCount.keySet());
        typesSortedList.sort((a, b) -> typeCount.get(b) - typeCount.get(a));
        
        int answer = 0;
        for(Integer type : typesSortedList) {
        
            k -= typeCount.get(type);
            answer++;
            
            if(k <= 0) break;
        }
        
        return answer;
    }
}

 

해결 코드 1

• List의 지네릭을 'Map.Entry<Integer, Integer>' 타입으로 선언해주면, 정렬의 기준을 key값으로 할지, value값으로 할지 정할 수 있기는 하지만, 이 문제에선 value값을 기준으로 내림차순 정렬을 하면 되기 때문에 그럴 필요까지는 없는 것 같다

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        
        HashMap<Integer, Integer> typeCount = new HashMap<>();
        for(int t : tangerine)
            typeCount.put(t, typeCount.getOrDefault(t, 0) + 1);
        
        List<Map.Entry<Integer, Integer>> entryList = new ArrayList<>(typeCount.entrySet());
        entryList.sort((a, b) -> typeCount.get(b.getKey()) - typeCount.get(a.getKey()));
        
        int answer = 0;
        for(Map.Entry<Integer, Integer> entry : entryList) {
        
            k -= entry.getValue();
            answer++;
            
            if(k <= 0) break;
        }

        return answer;
    }
}

 

해결 코드 2

• Wrapper class 객체를 이용하여 정렬하는 방식을 이용한 코드도 작성해보았다

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
    
        HashMap<Integer, Integer> typeCount = new HashMap<>();
        for (int t : tangerine)
            typeCount.put(t, typeCount.getOrDefault(t, 0) + 1);
        
        Integer[] typesArray = new Integer[typeCount.size()];
        int index = 0;
        for (int type : typeCount.keySet()) {
            typesArray[index] = type;
            index++;
        }
        
        Arrays.sort(typesArray, (a, b) -> typeCount.get(b) - typeCount.get(a));
        
        int answer = 0;
        for (int type : typesArray) {
        
            k -= typeCount.get(type);
            answer++;
            
            if (k <= 0) break;
        }
        
        return answer;
    }
}

---

▼ 정리

 

• 컬렉션에 값을 저장할 때 해시함수의 데이터를 저장한다면, 굳이 'add()'를 써서 데이터를 일일이 넣어주지 않고 'keySet()'이나 'entrySet()' 등을 이용해 객체를 생성하면서 저장해줄 수 있다는 것을 기억해두자
  
  
• 기본 정렬(오름차순) 외에 정렬(ex. 내림차순)을 할 때엔 Array의 경우 Wrapper class 타입이나 List로 변환해주고 해야 한다는 번거로운 점이 있었지만, 위처럼 애초에 List 객체를 생성해주고 해당 참조 변수로 'sort()'를 호출해준다면, 'Arrays.sort()'가 아닌 'Collections.sort()'를 호출하기 때문에 람다식으로 설정한 새로운 정렬 기준으로 바로 정렬 가능하다는 것을 기억해두자!
  ( 기본형 배열이 아닌 Wrapper class 객체를 생성해줘도 쉽게 바로 원하는 정렬 조건에 따라 정렬이 가능하다 )

(참고) [Algorithm] Arrays.sort(), Collection.sort() (+ 참조 지역성, cache) — Uykm_Note (tistory.com)

[Algorithm] Arrays.sort(), Collection.sort() (+ 참조 지역성, cache)

 

• 이 문제를 풀어보면서 'ArrayList<> al = new ArrayList<>();'와 'List<> l = new ArrayList<>();'의 차이가 궁금해서 이에 대해 한 번 찾아보았다
  
  ArrayList<> al = new ArrayList<>(); 
  ➜ ArrayList와 List에 선언된 메서드들을 모두 호출할 수 있다는 장점이 있지만, 'al = new LinkedList();' 같은 것이 불가능하다는 단점이 있다!
  
  List<> l = new ArrayList<>();
  ➜ List interface 안에 선언된 메서드들만 호출할 수 있다는 단점이 있지만, 'al = new LinkedList();'와 같은 접근이 가능하다는 장점이 있다!