[Algorithm] 프로그래머스_특이한 정렬(JAVA), 우선순위 큐, Comparator

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

프로그래머스

---

이 문제의 접근은 n과 배열의 차이값을 구하자는 아이디어로부터 시작됐다.

[-3, -2, -1, 0, 1, 2] 이런 식으로 차이값이 들어있는 배열을 생성할 수 있을 것이다.

이후 우선순위 큐가 생각났고, 절대값으로 우선순위를 매기되 같은 값이면 양수가 우선순위가 되도록 설정하였다.

 

여기서 Comparator 반환값에 대해 맨날 헷갈려서 정리하려고 한다.

PriorityQueue는 내부적으로 Comparator 인터페이스를 사용하고

Comparator 인터페이스의 핵심 메서드가 바로 compare이다.

PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer a, Integer b) {
        ...
    }
});

중요한 키포인트💫

음수	첫번째 매개변수 a가 왼쪽에 와야함
0	동일하다.
양수	첫번째 매개변수 a가 오른쪽에 와야함

 

PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer a, Integer b) {
        return a-b;
    }
});

위와같이 a-b를 반환값으로 설정하면

a<b 일 때 음수가 되고 a,b 순으로 정렬되므로 오름차순이다.

 

만약 b-a라면?

PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
    @Override
    public int compare(Integer a, Integer b) {
        return b-a;
    }
});

b<a 일 때 음수가 되고 a,b 순으로 정렬되므로 내림차순이 되는 것이다!!

 

gpt한테 물어봐도 헷갈렸었는데 

https://blog.naver.com/gaussian37/220514246243

JAVA, Comparator 에서의 반환값

이 분의 표를 보고 단 번에 이해했다. 감사합니다..

 

우선순위 큐로 정렬까지 했다면 각 배열의 원소 값에 n을 더해주면 정답이다.

 

아래는 정답소스⭕

import java.util.PriorityQueue;
class Solution {
    public int[] solution(int[] numlist, int n) {
        int[] answer = new int[numlist.length];
        int[] diff = new int[numlist.length];
        for(int i = 0; i < numlist.length; i++){
            diff[i] = numlist[i] - n;
        }
        
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> {
            int absA = Math.abs(a);
            int absB = Math.abs(b);
            
            if(absA != absB){
                return absA - absB;
            }else{
                return a > b ? -1 : 1;
            }
        });
        
        for(int num : diff){
            pq.add(num);
        }
        
        int idx = 0;
        while(!pq.isEmpty()){
            answer[idx++] = pq.poll() + n;
        }
        
        return answer;
    }
}