[리트코드] 0708

https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/608/week-1-july-1st-july-7th/3805/

n x n 행렬이 주어지고, 행렬의 각 열과 행은 정렬되어 있는 상태이다.

이 때, 행렬에서 k 번째로 작은(unique 하지 않게) 원소를 구하는 문제였다. 

 

그냥 행렬 돌면서 벡터에 넣어서 정렬해서 풀었다. 이미 정렬된걸 이용하면 더 빨리 정렬할 수 있는 방법이 있을거 같은데 몰라서 일단 저렇게 풀었다.

이진 탐색으로도 풀 수 있는 듯하다

 

코드

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n=matrix.size();
        vector<int> v;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                v.push_back(matrix[i][j]);
            }
        }
        sort(v.begin(), v.end());
        return v[k-1];
    }
};