[LeetCode] 1005. Maximize Sum Of Array After K Negations

https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/

Maximize Sum Of Array After K Negations - LeetCode

priorityQueue 를 사용하면 쉽게 풀 수 있다.

 

처음엔 Array를 계속 정렬했는데 그럴 필요가 없음.

 

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0; i < nums.length; i++) {
            pq.offer(nums[i]);
        }

        while(k > 0) {
           pq.offer(pq.poll() * -1);
            k--;
        }
        int sum = 0;
        while(!pq.isEmpty()) {
            sum += pq.poll();
        }
        return sum;
    }
}

 

 

 

1트 :  Array를 정렬하면서 풀었을 경우

2트 : PriorityQueue를 사용하여 풀었을 경우 

앞으로 문제를 풀 때 시간복잡도를 한번 더 생각하고 풀어야겠음.