[leetcode] 1337. The K Weakest Rows in a Matrix

문제해석

m x n 매트릭스가 주어지고 각 값이 1(병사), 0(시민)으로 할당된다

병사는 항상 시민 앞쪽에 있을 수 있으므로 행렬에서 모두 왼쪽에 위치한다.

이 때 병사의 수에 따라서 약함이 결정된다

예

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]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 2 
- Row 1: 4 
- Row 2: 1 
- Row 3: 2 
- Row 4: 5 
The rows ordered from weakest to strongest are [2,0,3,1,4].

인 경우 각 병사의 수에 따라서 0번 줄은 병사가 2, 1번줄은 병사가 4...

순으로 정렬했을 떄 약한 줄부터 순서를 나열하면 [2,0,3,1,4]가 되는데

 

주어진 k만큼 약한순서대로 출력한다고 했을 때

k가 3이면 [2,0,3]을 output으로 반환하면 된다.

 

정답 예

public int[] kWeakestRows(int[][] mat, int k) {
    // 길이는 변수 미리 할당
    int length = mat.length;

    // 각 줄별로 병사의 수를 기록
    int[] line = new int[length];

    for (int i = 0; i < length; i++) {
        // 1의 자리수에 줄 순서를 기록
        line[i] = i;
        for (int j=0; j< mat[i].length; j++) {
            if (mat[i][j] == 1) {
                // 병사(숫자1)의 수만큼 1000씩 더함
                line[i] += 1000;
            } else {
                // 최초로 시민(숫자0)이 발견된 경우 해당 줄 카운트를 벗어남
                break;
            }
        }
    }

    // 1000 * 병사의 수 + 줄 수로 정렬 (작은 순)
    Arrays.sort(line);


    int[] output = new int[k];
    for (int i = 0; i < k; i++) {
        // output 에는 작은 순으로 정렬 된 값에서 줄 수만 기록 
        output[i] = line[i] % 100;
    }
    return output;
}

 

이번에 풀어본 문제에서는 m(줄 수)가 100 이하인 점을 토대로 줄수를 기록하고 100으로 나눈 나머지가 줄 수가 되게끔 하는 꼼수(?)를 써서 줄 수를 따로 기록하는 부분은 좀 줄여보았다.

줄 수가 훨씬 더 크다면 다른 방법을 생각해봐야 할듯하다.