[99클럽 코테 스터디 32일차 TIL] #정렬7

32일차입니다. 어제 오늘 눈이 많이 내렸더라구요. 올해 첫눈인데 눈이 너무 많이 와서 놀랐어요.
첫눈을 올해도 혼자.. 크흠
짜증나니까 공부라도 열심히 해보겠습니다 ㅎ.
 

문제 설명

---

 
음 요약하자면,, HINDEX값을 구하는겁니다. 이게 무엇이냐면.. 논문 n편 중 h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값을 hindex라고 하는데 이를 구하라는 문제입니다. 참 쉽죠?
 
 

생각 흐름

---

우선 문제를 읽는데 처음 보는 개념을 설명을 하길래 쭉 따라서 읽어보았습니다.
근데 문제를 읽어도 읽어도 무슨 소리인지 이해를 못해서 처음에 조금 헤맸던 것 같습니다.
 
배열이 주어지고.. h번 이상 인용된 논문 -> 그니까 h보다 큰 요소의 개수가 h편 이상이다.
즉, h보다 큰 요소가 h개 이상인 것의 최댓값을 구하라는 문제였습니다.
 
그래서 저는 우선순위 큐를 이용해서 풀어보려고 우선 마구마구 적기 시작했습니다.
 
뭔가 가장 큰 값을 기준으로 하나씩 점검하며 푸는 문제같아서 내림차순으로 우선순위 큐를 선언해주고 이를 이용해 풀어봤습니다.
 
어,, 우선 cnt라는 정수형 변수를 1로 선언해주었습니다. 자기자신도 포함하여 큰 수를 카운팅해야하니까 1로 선언했고 이를 이용해 pq.top()과 조건문을 걸어주었습니다. 
 
그렇게 했더니 어찌하여 정답을 내는 코드를 작성해서 마무리를 했었습니다.

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    priority_queue <int> pq; // 내림차순으로 정렬한 우선순위 큐 pq 선언
    
    for (auto i : citations) {
        pq.push(i); // 내림차순으로 정렬
    }
    
    int cnt = 1; // 해당 문서보다 더 많이 인용된 문서 수 cnt (자기 자신을 포함하니까 1)
    while (!pq.empty()) {
        if (pq.top() <= cnt) {
            answer = pq.top();
            break;
        }
        pq.pop();
        cnt++;
    }
    return answer;
}

 
하지만 실패가 떠버렸고 뭔가 얼렁뚱땅 짠 코드답게 모든 상황에서 정답을 도출하지는 못하는 잘못된 코드라는 것을 깨달았습니다.
 
그래서 갈아엎어버렸습니다.
 
결국 몇번째로 큰 수의 "인덱스"와 "그 수"의 대소비교가 중요하므로, 그냥 벡터로 내림차순 정렬을 해서 풀자는 생각을 하였고 citations 벡터를 반복문으로 돌면서 i+1보다 citations[i]가 큰 경우 answer++를 해주고 아닌 경우, break를 해주며 마무리하였습니다.
 
아마 문제를 정확히 이해하셨다면 코드가 무슨 말인지 아실거라고 생각합니다.
 

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

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    
    // 결국은 h번째로 큰 수가 h일때를 찾는다는 거죠
        
    sort (citations.begin(), citations.end(),greater<int>()); // 내림차순으로 정렬
    
    for (int i = 0; i < citations.size(); i++) {
        if (citations[i] >= i+1) {
            answer++;
        }
        else {
            break;
        }
    }
    return answer;
}

 
 

공부한 내용 정리

---

sort()는 기본적으로 오름차순 정렬이 되기 때문에, sort()에서 내림차순정렬을 하고 싶을땐, 마지막 조건에 greater<int>()를 붙여주면 됩니다.
 
사실 정렬에 관한 내용은 많이 공부를 해서 뭔가 더이상 쓸만한 내용이 없었습니다 ㅎ..