99클럽 코테 스터디 23일차 TIL - 786 K-th Smallest Prime Fraction

786. K-th Smallest Prime Fraction / c++ / Medium / 14분

문제 및 코드

#include <iostream>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        vector<vector<int>> vec;

        for (int i = 0; i < arr.size(); ++i)
        {
            for (int j = i + 1; j < arr.size(); ++j)
            {
                vec.push_back({arr[i], arr[j]});
            }
        }

        sort(vec.begin(), vec.end(), [](vector<int>& a, vector<int>& b)->bool
        {
            return a[0] * b[1] < b[0] * a[1];
        });

        return vec[k-1];
    }
};

접근 방식

정렬

1. 문제는 1과 소수로 이루어진 정렬된 배열에서 원소 2개를 겹치지 않게 뽑아서 분수 (분자/분모 순) 을 만들었을 때, k 번째로 작은 수가 되는 경우를 구하는 것이었다.
2. 일단 조합의 모든 경우를 다 새로운 vector<vector> vec에 넣어준다.
3. 그리고 정렬을 할 때, a[0] * b[1] < b[0] * a[1] 식으로 정렬해준다. (결국 분수의 비교라 함은, 분모가 같은 상황에서 분자의 값이 작은 경우이고, 분모가 같으려면 두 분수의 분자 분모에 각 수를 곱해주면 되므로)
4. 그런뒤 vec[k-1]을 반환 (0부터 시작하므로)

생각해 볼 점

1. 이분 탐색 문제로 내준건데, 단순 정렬로도 풀 수 있어서 생각보다 빨리 풀었다. (효율은 떨어지지만)

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL