<aside> 💡 문제 링크

</aside>

문제 정리

<aside> 💡 문제

1(군인을 나타냄)과 0(민간인을 나타냄)으로 구성된 m x n 이진 행렬 매트가 제공됩니다. 군인들은 민간인 앞에 배치됩니다. 즉, 모든 1은 각 행의 모든 0 왼쪽에 나타납니다.

다음 중 하나가 참인 경우 행 i는 행 j보다 약합니다.

i행의 군인 수는 j행의 군인 수보다 적습니다. 두 행 모두 군인 수는 같고 i < j입니다. 가장 약한 것부터 강한 것 순으로 행렬에서 가장 약한 k개 행의 인덱스를 반환합니다.

</aside>

예제로 정리

<aside> 💡 입력값 mat는 m x n 으로 된 이진 행렬 매트이다.

각 행에서 1의 숫자가 합이 가장 적은 k개 행의 인덱스를 반환한다.

</aside>

Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]

접근방법

<aside> 💡 1. 각 행의 숫자를 모두 더해 리스트화 시킨다.

1. 이진 최소 힙으로 구현한다.
2. k만큼 추출한다. ( 최소 힙이기 때문에 최소값부터 추출된다.)
3. 기본 리스트에서 인덱스를 찾는다. </aside>

코드 진행

• 전체코드

<aside> 💡 mat의 각 행을 더한 값을 1차원 리스트로 생성해준다.

</aside>

def kWeakestRows(self, mat, k):
        results = []

        # (1) 각 행 숫자를 더해 리스트 생성
        list = [sum(row) for row in mat]

<aside> 💡 heapq.heapify()를 사용해서 바로 리스트를 최소 힙으로 구현해준다.

원본 리스트의 복사본을 생성해서 추후 인덱스 비교에서 사용한다.

(heapify()를 사용해서 index함수 사용 불가)

</aside>

# 인덱스를 비교하기 위해 복사본 생성
        list_copy = list[:]

        # (2) 힙 생성
        heapq.heapify(list)