[코딩테스트] 예산, Arrays.sort() | 프로그래머스

문제

✍🏻 문제 바로가기

문제	레벨	정답률
예산	Lv.1	76%

My Code

import java.util.*;

class Solution {
    public int solution(int[] d, int budget) {
        int answer = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        
        for(int i : d){
            queue.add(i);
        }
        
        int sum = 0;
        while(sum <= budget){
            if(queue.isEmpty()){
                return answer;
            } else{
                sum += queue.poll();
                answer++;
            }
        }
        
        return --answer;
    }
}

오름차순으로 정렬을 하기 위해서 우선순위 큐를 사용하였다.
그리고 sum이라는 변수에 차례대로 더하면서 예산과 비교해나갔고, answer 횟수를 1씩 증가하였다.
그런데 이런식으로 하면 예산을 전부 쓰는 경우가 아니라면, 마지막에 answer가 한 번 더 연산이 되어 마지막에 1을 빼주었다.

최적화 코드

import java.util.Arrays;

class Solution {
    public int solution(int[] d, int budget) {
        Arrays.sort(d);  // 배열을 오름차순으로 정렬
        
        int sum = 0;
        int answer = 0;
        
        for (int cost : d) {
            if (sum + cost > budget) {
                break;  // 예산을 초과하면 종료
            }
            sum += cost;
            answer++;
        }
        
        return answer;
    }
}

나의 코드를 최적화시킨 코드이다.
이 문제의 경우엔 굳이 우선순위 큐를 사용할 필요가 없었다.
배열의 sort() 메서드를 사용하면 좀 더 쉽게 정렬이 가능하다.

• Arrays.sort()
  

while 문 대신 for 문으로 변경하면서 마지막에 answer값을 1 빼주어야 했던 문제도 해결되었다.

PriorityQueue와 Arrays.sort()

이쯤에서 우선순위큐와 Arrays.sort()의 차이점과 어떨 때 사용하면 효과적인지 정리해보았다.

Arrays.sort()

배열을 정렬하는 데 사용됨
정렬하고 나면 오름차순이나 내림차순으로 순서 고정
정렬 시간 복잡도는 평균적으로 O(n log n)

❔ 언제 사용해야 할까?

1. 전체 배열을 정렬해야 하는 경우

2. 최소값 또는 최대값을 여러 번 사용할 필요가 없는 경우

3. 한 번 정렬 후 정렬된 순서로 순회가 필요한 경우

   • 작은 값부터 차례대로 처리 등

PriorityQueue

힙 자료 구조를 사용하여 우선순위가 높은 원소를 빠르게 접근
최소 힙으로 작동하여 가장 작은 원소를 우선 처리
삽입과 삭제의 시간 복잡도는 O(log n)

❔ 언제 사용해야 할까?

1. 최소값 또는 최대값을 빈번하게 필요로 하는 경우

2. 정렬된 상태로 유지하면서 동적으로 데이터를 추가/삭제해야 하는 경우

3. 일부 원소만 정렬된 순서로 처리해야 하는 경우

⭐ 정리

• Arrays.sort()는 정렬된 상태에서 순회가 필요한 경우에 적합
• PriorityQueue는 동적으로 원소를 추가/삭제하면서 최소값과 최대값을 자주 필요로 하는 경우에 적합

=> 위의 문제에서는 단순히 정렬이 목적이고, 최소값이나 최대값을 필요로 하는 문제는 아니기에 Arrays.sort()가 더 적합한 경우에 해당!

---

알고 있던 개념일지라도 어떤 상황일때 사용하기 적합한지는 잘 모르는 경우가 많다. 그리고 Arrays.sort() 매서드의 경우 기능이 한정적이라 차라리 PriorityQueue를 사용해왔었다.
그러나 Arrays.sort()를 쓰는 것이 더 적합한 경우가 있다는 것도 알게 되었고, 특정 문법만 편식하지 않도록 주의해야겠다고 생각했다.