프로그래머스 - H-Index(C++)

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42747

문제 난이도

Lv 2

문제 접근법

문제 속 h번 이상 인용된 논문이 h편 이상에 주목해야 한다.
h번은 배열 속 숫자도 아니고 그저 0부터 시작한 숫자가 논문 h편 이상이 되는 걸 찾으면 된다.
여기서도 앞서 썼던 vector container sort greater<int>()를 썼다.

추가한 라이브러리
algorithm

통과 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    sort(citations.begin(), citations.end(), greater<int>());
    
    for(int i=0; i<citations.size(); i++){
        if(answer >= citations[i]) break;
        answer++;
    }
    return answer;
}

피드백

오해

배열 속에 숫자를 이용해 구하는 줄 알고 이분탐색을 사용했다.

그리고 테스트 코드 통과하고 테스트케이스들을 돌리는데 테스트 9번에서 자꾸 실패가 떴다. 왜 실패인지 몰라서 하단에 질문하기에 들어갔는데 나 빼고 ㅋㅋㅋ 67명이나 질문을 올린걸 보고 동지애를 느꼈다.
누가 문제 풀기 팁이라고 배열 속 숫자로 쓰는게 아니라는 걸 보고 그럼 당연히 배열 속 숫자가 답이 아니지 그럼 뭔데? 하다가 다른 분이 올려주신 테스트 케이스 보고 알았다.

[31,66] 으로 값을 넣으면 2편 이상 논문이 2번 이상 인용된거라 답(H-Index) 은 2다. -> 이 테케보고 아차 싶었다. 그럼 당연히 이분탐색으로는 통과가 안되는... 어쩐지 왜 카테고리가 정렬인가 했다.
나처럼 착각하고 다르게 풀었다가 통과안되는 분들은 저 테스트 케이스를 넣어보길 바란다.

이분탐색 이용한 코드(테케9를 통과못해서 실패)
아까워서 첨부하고 감 ㅠ

int solution(vector<int> citations) {
	int answer = 0;
	sort(citations.begin(), citations.end());

	int left = citations[0];
	int right = citations[citations.size() - 1];

	while (left <= right) {
		int mid = (left + right) / 2;
		int cnt = 0;
		for (int i = 0; i < citations.size(); i++) {
			if (mid <= citations[i]) cnt++;
		}
		if (cnt >= mid) {
			left = mid + 1;
			if (answer < mid) answer = mid;
		}
		else {
			right = mid - 1;
		}
	}
	return answer;

}