[LeetCode] 1380. Lucky Numbers in a Matrix

https://leetcode.com/problems/lucky-numbers-in-a-matrix/description/

leetcode - Lucky Numbers in a Matrix

문제 유형 : 행렬

문제 난이도 : Easy

 

문제

Given an m x n matrix of distinct numbers, return all lucky numbers in the matrix in any order.

A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

 

m x n의 행렬이 주어진다.

럭키넘버들을 찾아서 반환하시오. 순서는 상관없습니다.

 

럭키넘버는 한 행에서 가장 작아야 하고, 한 열에서 가장 커야 합니다.

 

풀이

한 행마다 가장 작은 수를 찾아서, 그 수의 열에서 그 수가 가장 큰지 확인하고 그렇다면 배열에 담으면 된다.

 

코드

C++

class Solution {
private:
    int m, n;
public:
    bool isMaxima(int row, int col, vector<vector<int>>& matrix) {
        int maxIdx = 0;
        int maximum = matrix[0][col];
        for(int i = 1; i < m; i++) {
            if(maximum < matrix[i][col]) {
                maxIdx = i;
                maximum = matrix[i][col];
            }
        }

        return maxIdx == row;
    }

    vector<int> luckyNumbers(vector<vector<int>>& matrix) {
        vector<int> ans;
        m = matrix.size();
        n = matrix[0].size();

        for(int i = 0; i < m; i++) {
            int minIdx = 0;
            int minimum = matrix[i][0];
            for(int j = 1; j < n; j++) {
                if(minimum > matrix[i][j]) {
                    minIdx = j;
                    minimum = matrix[i][j];
                }
            }
            if(isMaxima(i, minIdx, matrix)) ans.push_back(minimum);
        }

        return ans;
    }
};

// 3 7 8
// 9 11 13
// 15 16 17