귤 고르기

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

문제 설명

• 주어진 파라미터: int k, int[] tangerine
• 반환값: int
• 수확한 귤 중 k 개를 골라 상자 하나에 담아 판매하려 한다.
• 귤을 크기별로 분류했을때 서로 다른 종류의 수를 최소화하고싶다.
• [1,3,2,5,4,5,2,3] → 귤 6개를 판매하고 싶다면 크기가 1,4인 귤을 제외한 여섯개의 귤을 담으면 종류가 3가지가 되어 다른종류가 최소가 된다.
• 서로다른 종류의 수의 최솟값 return
• 1 ≤ k ≤ tangerine의 길이 ≤ 100000 → $10^5$ → 귤 개수
• 1 ≤ tangerine의 원소 ≤ 10000000 → $10^7$ → 크기 개수

풀이 방식

1. 원소의 길이가 길어 수행시간을 고려해야한다. → 어떻게?
2. 종류별로 몇개가 있는지 파악해야한다.
3. map? list?
   1. map으로 하면 종류 최대 개수는 어떻게 구할건데?
   2. list로 하면 sort에 시간이 많이 걸릴텐데?
   3. priorityQueue에 [크기종류, 개수] 넣고 개수를 기준으로 많은걸 꺼내오면서 정리한다면?
      1. priorityQueue를 map 처럼 크기종류를 기준으로 개수를 변경할 수 있나?
4. Map으로 종류별 개수를 저장해두고 PriorityQueue에 넣어 최대 개수 판별

코드

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        
        Map<Integer, Integer> m = new HashMap<>();
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        
        for(int i : tangerine){
            // m 내에 해당 key가 존재하지 않을 경우 
            if(m.get(i) == null){
                // System.out.println("새로운 값 삽입");
                m.put(i, 1);
            }else{
                // System.out.println("기존 값 변경");
                int v = m.get(i);
                m.put(i,v+1);
            }
        }
        
        // Map 순회하며 pq에 넣기 
        int answer = 0; // 카운트값
        
        for(int num : m.values()){
            pq.offer(num);
        }
        
        while(k > 0){
            k -= pq.poll();
            answer++;
        }
        
        return answer;
    }
}

회고

map을 순회하는 방법에서 많이 헤맸던것 같다

[HahsMap의 주요 메소드]

• size: map의 크기를 알려줌
• get
• put
• remove
• getOrDefault
• putIfAbsent
• isEmpty

map을 순회하는 방법

1. Iterator 사용

   Map<Integer, Integer> map = new HashMap<>();
   
   Iterator<Integer> keys = map.keySet().iterator();
   for(keys.hasNext()){
   	int key = keys.next();
   	map.get(key);
   }

2. entrySet으로 접근하기

   Map<Integer, Integer> map = new HashMap<>();
   
   for(Map.Entry<Integer, Integer> entry : map.entrySet()){
   	int key = entry.getKey();
   	int value = entry.getValue();
   	
   }

3. keySet을 이용해 접근하기

   Map<Integer, Integer> map = new HashMap<>();
   
   for(Integer i : map.keySet()){
   	map.get(i);
   }

---

기억해 두자구잇~