Delete Greatest Value in Each Row

문제 : Delete Greatest Value in Each Row

정수값으로 이루어진 이중배열을 주고, 각 배열들에서 가장 큰 수대로 숫자 하나씩을 뽑은 뒤 비교하여 가장 큰 수들의 합을 return 하는 문제이다.

ex)
Input : [[1,2,4],[3,3,1]]
output : 4 + 3 + 1 = 8

첫번째 풀이

var deleteGreatestValue = function(grid) {
    let m = grid.length //grid row의 총 길이
    let n = grid[0].length //grid height의 총 길이
    let res = 0

	//이차원배열의 길이 동안
    while(n > 0){
        let max = 0
        //일차원배열의 길이 동안 
        for(let i = 0 ; i < m ; ++i){
          	//이차원배열중 최대값 가져옴
            let arrNum = Math.max(...grid[i])
            //인덱스 가져와서 제거함
            grid[i].splice(grid[i].indexOf(arrNum),1)

            if(max < arrNum){
                max = arrNum
            }
        }

      	//가장 큰수를 더함
        res += max
        n--
    }

    return res
};

시간복잡도

최대 값을 찾고 Math.max(...grid[i]), 인덱스를 찾고 grid[i].indexOf(arrNum),1, 값을 제거하고 grid[i].splice(index, 1) 이 모든 행위는 각각 n의 작업이므로 O(n + n + n) = O(3n)= O(n) 이 과정을 각 행에 대해 수행하므로 O(m n), 또한 while loop는 O(n)번 반복되므로, 전체 시간복잡도는 O(n m n) = O(m n^2)

두번째 문제풀이

우선순위 큐를 활용한 문제풀이

var deleteGreatestValue = function (grid) {
    var pqs = [], res = 0
    // 각 이중배열을 우선순위큐 형태로 만든다( 높은값 순으로 정렬된다 )
    for (let row of grid) {
        let pq = new MaxPriorityQueue()
        for (let val of row) pq.enqueue(val)
        pqs.push(pq)
    }

    //하나씩 빼면서 최대값을 max에 넣고 max를 다시 비교해서 최대값을 구한다
    while (pqs[0].size() > 0) {
        let max = 0
        for (let pq of pqs) max = Math.max(pq.dequeue().element, max)
      	//구한값을 모두 더한다
        res += max
    }
    return res
};

시간복잡도

각 요소를 enqueue하는데 O(log n)의 시간이 걸리며, 행의 길이가 n일 때 n개의 요소를 'enqueue하므로, 한 행에 대해 O(n log n)의 시간이 걸림, m개의 행에 대해 과정이 반복되므로, 전체 초기화 시간 복잡도는 O(m * n logn)