리트코드 데일리과제(3/24) - Advantage Shuffle

leetcode.com/explore/challenge/card/march-leetcoding-challenge-2021/591/week-4-march-22nd-march-28th/3683/

1. 유형

우선순위큐

 

2. 풀이

- B의 데이터 보다 A배열이 최소의 차이로 큰 값을 찾으면 됩니다.

 

이를 위해서, A를 정렬

 

B는 우선순위큐를 사용해서 정렬

 

마지막으로 A배열에서 투포인터를 사용

 

3. 코드

class Solution {
    
    public int[] advantageCount(int[] A, int[] B) {
        int answer[] = new int[A.length];
        Arrays.sort(A);
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                return -(o1[0]-o2[0]);
            }
        });
        int index=0;
        for(int b: B){
            pq.add(new int[]{b,index++});
        }
        int low=0;
        int high = A.length-1;
        while(low <= hight){
            int temp[] = pq.poll();
            if(A[high] > temp[0]){
                answer[temp[1]] = A[high--];
            }else{
                answer[temp[1]] = A[low++];
            }
        }
        return answer;
    }
}

 

모범답안

class Solution {
    public int[] advantageCount(int[] A, int[] B) {
        int[] sortedA = A.clone();
        Arrays.sort(sortedA);
        int[] sortedB = B.clone();
        Arrays.sort(sortedB);

        // assigned[b] = list of a that are assigned to beat b
        Map<Integer, Deque<Integer>> assigned = new HashMap();
        for (int b: B) assigned.put(b, new LinkedList());

        // remaining = list of a that are not assigned to any b
        Deque<Integer> remaining = new LinkedList();

        // populate (assigned, remaining) appropriately
        // sortedB[j] is always the smallest unassigned element in B
        int j = 0;
        for (int a: sortedA) {
            if (a > sortedB[j]) {
                assigned.get(sortedB[j++]).add(a);
            } else {
                remaining.add(a);
            }
        }

        // Reconstruct the answer from annotations (assigned, remaining)
        int[] ans = new int[B.length];
        for (int i = 0; i < B.length; ++i) {
            // if there is some a assigned to b...
            if (assigned.get(B[i]).size() > 0)
                ans[i] = assigned.get(B[i]).pop();
            else
                ans[i] = remaining.pop();
        }
        return ans;
    }
}

 

 

4. 배운점

 

우선순위큐를 사용할 때, 람다를 사용하면 더 깔끔함.