[프로그래머스/Java] 귤 고르기

 

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

프로그래머스

 

---

처음 코드

import java.util.*;

public class Solution {
    
    private final int MAX = 10_000_000;

    private class Tangerine implements Comparable<Tangerine> {
        private int type;
        private int cnt;

        public Tangerine(int type, int cnt) {
            this.type = type;
            this.cnt = cnt;
        }

        public void updateCnt() {
            this.cnt++;
        }
        
        public int getCnt() {
            return this.cnt;
        }

        @Override
        public int compareTo(Tangerine o) {
            return o.cnt - this.cnt;
        }
    }

    public int solution(int k, int[] tangerine) {
        Tangerine[] tangerines = new Tangerine[MAX+1];
        for (int i=0; i<=MAX; i++) {
            tangerines[i] = new Tangerine(i, 0);
        }
        
        for (int i : tangerine) {
            tangerines[i].updateCnt();
        }
        Arrays.sort(tangerines);

        int answer = 0;
        int sum = 0;
        for (int i=0; i<=MAX; i++) {
            answer++;
            sum += tangerines[i].getCnt();
            if (sum >= k) {
                break;
            }
        }
        return answer;
    }
}

 

(귤의 종류, 개수) 를 가진 클래스를 선언해주고, Comparable 을 implement 하여 개수를 기준으로 내림차순 정렬

=> tangerine 원소의 최댓값을 크기로 가지는 배열을 만들기 때문에 비효율적.

 

 

---

변경 코드

 

import java.util.*;
import java.util.stream.*;

public class Solution {
    public int solution(int k, int[] tangerine) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : tangerine) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }

        List<Integer> list = map.values().stream().collect(Collectors.toList());
        Collections.sort(list);
        
        int size = list.size();
        int answer = 0;
        int cnt = 0;
        
        for (int i=size-1; i>=0; i--) {
            answer++;
            cnt += list.get(i);
            
            if (cnt >= k) {
                break;
            }
        }
        return answer;
    }
}

 

HashMap을 이용하여 귤의 개수 저장 후 개수만 정렬

 

 

훨씬 빨라졌다..