[PRG] 138476 귤 고르기 JAVA

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

프로그래머스

 

<해시맵 사용>

메모리: 104 MB

실행시간: 42.74 ms

 

<배열 사용>

메모리: 138 MB

실행시간: 66.50 ms

 

문제분석

그리디하게 풀면 될 것 같다 !

1. 귤 크기별로 카운트를 저장한다.
2. 정렬한다.
3. 개수가 많은 크기부터 차례대로 채운다.

귤 개수가 최대 100,000 이므로,
정렬에서 O(NlogN) 만큼 사용해도 시간초과는 안난다 !

 

걸린시간

30분 ⏱️

 

풀이방법

메모리와 실행 시간에서 어떤 차이가 있을 지 궁금해서 두 가지 방식으로 풀었다 😎

<해시 맵 사용>
1. 해시맵 선언
2. 귤 배열 카운트
3. 카운트 값 정렬을 위해 리스트에 옮기기
4. 리스트 정렬
5. 리스트 순회하며 종류 구하기

-------------------------------------------------------------------

<배열 사용>
1. 10000001 크기의 배열 선언
2. 귤 배열 카운드
3. 배열 정렬
4. 배열 순회하며 종류 구하기

-------------------------------------------------------------------

📌 그 결과 해시 맵을 사용하는 게 더 효율적이었다 ^^...
코드의 가독성이나 짜임새는 배열을 쓰는게 더 좋아보였으나
효율 측면에서는 해시 맵이 더 나았다

 

포인트

단순히 우선순위대로 귤을 채우면 되는 문제이다 ^~^ 매우 그리디하죠 ~?
더 효율적인 방법이 있을 것 같은데 아시는 분은 댓글 달아주세요 ... 🙇‍♀️

 

코드

<해시 맵>

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        // 크기별 카운트 저장할 해시맵
        Map<Integer, Integer> map = new HashMap<>();
        // 귤 배열 카운트
        for(int i = 0; i < tangerine.length; i ++) {
            if(map.containsKey(tangerine[i])) {
                map.replace(tangerine[i], map.get(tangerine[i]) + 1);
            } else {
                map.put(tangerine[i], 1);
            }
        }
        // 카운트 값 정렬
        List<Integer> list = new ArrayList<>(map.values()); // 리스트에 value 옮기기
        Collections.sort(list, Collections.reverseOrder()); // 내림차순 정렬
        // 리스트 돌면서 종류 구하기
        int cnt = 1;    // 종류
        int sum = 0;    // 귤 개수
        for(int i = 0; i < list.size(); i ++) {
            if(sum + list.get(i) >= k) {
                break;
            } else {
                sum += list.get(i);
                cnt ++;
            }
        }
        
        return cnt;
    }
}

 

<배열>

    public int solution(int k, int[] tangerine) {
        
        // 크기별 카운트 저장할 배열
        int[] count = new int[10000001];
        // 귤 개수 카운트
        for(int i = 0; i < tangerine.length; i ++) {
            count[tangerine[i]] ++;
        }
        // 카운트 값 정렬
        Arrays.sort(count); // 오름차순 정렬
        // 리스트 돌면서 종류 구하기
        int cnt = 1;    // 종류
        int sum = 0;    // 귤 개수
        for(int i = count.length - 1; i >= 0; i --) {
            if(sum + count[i] >= k) {
                break;
            } else {
                sum += count[i];
                cnt ++;
            }
        }
        return cnt;
    }
}