[프로그래머스 2019 KAKAO BLIND RECRUITMENT] (level1) 실패율

1). double 같은지 비교

• https://www.acmicpc.net/blog/view/37
• double 끼리 같은지 비교할때, abs(a - b) < 매우작은소수점오차
  이렇게 해야 한다.
• 그런데 여기서 좀 충격인게 위 글을 보고 1e-9 (0.000000001) 의 오차를 가지게 했는데
  실제 실행시킬때 테케 통과가 안되는 문제가 있었다.

이건 진짜 억울하다

 

• 그래서 EPS를 1e-15 까지 더 줄이니 통과 했다.

---

2). 풀이

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

const double DOUBLE_OFFSET = 1e-15;

bool comp(const pair<double, int>& lhs, const pair<double, int>& rhs) {
    if(abs(lhs.x - rhs.x) < DOUBLE_OFFSET) {
        return lhs.y < rhs.y;
    }
    return lhs.x > rhs.x;
}

vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    vector<pair<double, int>> failbyst;
    
    int userCnt = stages.size();
    sort(stages.begin(), stages.end());
    
    // for(const auto & e : stages) {cout << e << " ";} cout <<endl;
    
    for(int i = 1; i <= N; i++) {
        int lb = lower_bound(stages.begin(), stages.end(), i) - stages.begin();
        int ub = upper_bound(stages.begin(), stages.end(), i) - stages.begin();
        int ststepped = userCnt - lb;
        int ststuck = ub - lb;
        // cout << "N "  << i << " ststepped : " << ststepped << " ststuck : " << ststuck << endl;
        if(ststepped == 0) {failbyst.push_back({0.f, i});}
        else failbyst.push_back({(double)ststuck / (double)ststepped ,i});
    }
    sort(failbyst.begin(), failbyst.end(), comp);
    for(const auto& e : failbyst) {
        answer.push_back(e.y);
    }
    
    
    return answer;
}

 

프로그래머스는 백준이랑 다르게 오차 범위가 더 빡빡한가??아니면 카톡 문제가 유난히 이런것인지 또 배워간다.

 

 

---

3). 사용한 테케

---

4). 정렬된 배열 구간 원소 갯수 구하기

Upper_Bound, Lower_bound를 사용하면 구간 원소 개수 구할때 유용함