[프로그래머스] 과일 장수(java)

문제

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

프로그래머스

---

나의 풀이

import java.util.Arrays;

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        Arrays.sort(score);
        int scoreLen = score.length;
        int finish = scoreLen % m;
        while (scoreLen > finish) {
            scoreLen -= m;
            answer += score[scoreLen] * m;
        }
        return answer;
    }
}

배열을 오름차순으로 정렬하고 큰 점수부터 m묶음씩 박스를 포장한다. 그런데... 다 풀고보니 k가 왜 필요하지?라는 생각이 들어서 k 인자를 활용하여 다시 풀어봤다.

 

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int solution(int k, int m, int[] score) {
        int answer = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < score.length; i++) {
            if (map.get(score[i]) == null) {
                map.put(score[i], 1);
                continue;
            }
            map.put(score[i], map.get(score[i]) + 1);
        }

        int tmp = 0;
        for (int i = k; i > 0; i--) {
            if (map.get(i) == null)
                continue;
            int cnt = map.get(i);
            if (cnt + tmp < m) {
                tmp += cnt;
                continue;
            }
            if (tmp != 0) {
                cnt += tmp;
            }
            answer += (cnt / m) * m * i;
            tmp = cnt % m;
        }

        return answer;
    }
}

HashMap을 사용해서 사과 점수별 개수를 먼저 탐색했다. 그리고 k부터 1점까지 순회하면서 해당 점수대에 사과를 박스별로 포장하고 남은 사과 개수는 tmp로 보낸다. 다음 점수는 tmp 개수를 추가한 상태로 박스별 포장하고 다시 남은 개수를 tmp로 보내는... 이런 식으로 완성했다.

 

성능 테스트를 해봤다.

 

왼쪽이 정렬 후 박스 포장한 성능이고, 오른쪽이 HashMap을 사용한 성능이다. 메모리 사용은 비슷하지만 속도는 간단한 부분은 오른쪽이 확실히 조금 더 빠른 것을 알 수 있다. 아마 왼쪽은 정렬하는데서 조금 오래 걸린것이 아닌가 하는 생각이 든다. 

 

k인자가 주어졌으니 활용해보았고, 속도 차이도 알 수 있었다. k를 활용한 더 좋은 방법이 있을지 고민해보자. 있으면 알려주세요...