[프로그래머스] H-Index

1. 문제 설명

 

 

2. 이중 포문

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    unordered_map<int, int> m;
    
    for(int n : citations)
    {
        for(int i = 0; i <= n; ++i)
        {
           ++m[i];
        }
    }
    
        
    for(int i = 0; i <= 10000; ++i)
    {
        if(i <= m[i])
        {
            if(answer < i)
            {
                answer = i;
            }
        }
    }
    
    
    return answer;
}

논문의 수가 1000개 이하이고, 인용 횟수가 10,000이하라고 주어져서 높은 시간 복잡도 알고리듬을 요구하는 문제구나 싶었어요. 삼중 포문 쓸 생각까지 해야겠네 라고 예상을 했지만, 의외로 이중포문으로 해결할 수 있었습니다. 만약 인용횟수가 5로 주어지면 0~5까지의 "~이상 인용 횟수"를 1증가시켜주는 방식으로 작동합니다. 나름 논리적인 접근이라고 생각하며 만족했지만, 다른 사람의 풀이를 참고해보니 단일포문으로 해결하셨더군요 .. 어떻게 단일포문으로 푸는 알고리듬을 떠올리신 건지 ㅠㅠ

 

3. 단일 포문

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

using namespace std;

int solution(vector<int> citations) {
    sort(citations.begin(), citations.end(), greater<int>());

    for (int i = 0; i < citations.size(); ++i) {
        if (citations[i] < i + 1) {
            return i;
        }
    }

    return citations.size();
}

코드가 너무 간결해서 이해하는데 10분 정도 쓴 것 같아요 .. 이 분께서 작성하신 코드의 매커니즘은 다음과 같습니다.

인용 횟수를 기준으로 내림차순 정렬을 합니다. 이후 현재 원소가 해당 인덱스에 1을 더한 값보다 작다면 바로 해당 인덱스를 리턴하는 방식인데요. [3, 0, 6, 1, 5]가 테스트 케이스로 주어져서 이걸 예시로 들어보면, 내림차순 정렬을 통해 [6, 5, 3, 1, 5]가 되겠죠. 6은 현재 인덱스에 1을 더한 값인 1보다 크니 넘어갑니다. 5도 2보다 크기 때문에 넘어가고, 3은 3과 같으니 넘어가고 ! 1은 4보다 작아서 3을 return 하게 됩니다.

원래라면 세 번째 원소인 3과 비교하면서 return 하는게 더 직관적일 것 같은데, 알고리듬이 효율적이니까 인정이죠 ..