[leetcode 2024/02/08] 1337. The K Weakest Rows in a Matrix

https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/description/

LeetCode - The World's Leading Online Programming Learning Platform

1. 접근 방법 

input 으로 다음과 같이 mat, k 가 주어진다.

mat = 
[[1,1,0,0,0], #2 index = 0
 [1,1,1,1,0], #4 index = 1
 [1,0,0,0,0], #1 index = 2
 [1,1,0,0,0], #2 index = 3
 [1,1,1,1,1]],#5 index = 4
k = 3

 

이때, 1의 개수가 적은 index k개를 출력하는 것이다. 

index 2가 1개로 가장 적으므로, 2가 먼저 출력 될 것이다.

index 0이 2개로, 다음으로 적으므로 0 출력,

index 3이 2개로 , 다음으로 3 출력

 

이를 heap으로 접근해서 heap에 넣고 제일 작은 수 k개를 출력하는 방식으로 코드를 짰었다.

하지만, 뭔가 heap이 아니라 다른 방식으로 접근하는게 더 빠를 수 있을 것 같아서 다르게 풀어보았다. -> sort()

 

sort와 heap이 별 차이를 보이지 않았으며, 혹은 sort가 더 빠르게도 했다. 

python에서의 heap의 장점은 언제 보이는 것일까.

 

이를 알아보았다.

다른 언어의 경우 heap이 더 빠를지언정, python의 정렬함수가 매우 효율적으로 구현되어 있어서 일반적으로 빠른 성능을 보인다.

 

요약:

힙 -> 최소/최대 요소 관리, 우선순위 큐 등의 구현에서 좋은 성능을 나타낼 수 있다.

하지만 python 내부적으로 sort가 효율적으로 구현되어 있어서 sort가 더 좋은 성능을 빈번히 나타내기도 한다.

 

2. 코드

예제1: heap 이용

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        min_heap = []
        for i in range(len(mat)):
            heapq.heappush(min_heap, (Counter(mat[i])[1], i))

        heapq_k = heapq.nsmallest(k, min_heap)
        return list(map(lambda x: x[1],heapq_k))

 

예제2: sort 이용

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        one_num = []
        result = []
        for i in range(len(mat)):
            one_num.append([sum(mat[i]), i])

        one_num.sort()

        for i in range(k):
            result.append(one_num[i][1])

        return result