[백준 BOJ] 12109번 Hindeks (C++/cpp)

문제 설명

https://www.acmicpc.net/problem/12109

 

 

접근 방법 - 정렬을 활용한 배열 연산 문제

백준의 12109번 문제는 정렬과 배열을 함께 활용하여 해결해야 하는 문제이다.

해당 문제는, 어떤 과학자가 쓴 논문의 개수와 각 논문의 인용 수치가 입력으로 주어질 때 이 과학자의 h-index 값을 구하여 출력해야 하는 문제이다.

이때, "인용 수치가 H 이상인 H개 논문을 고를 수 있다."에 있어 H의 최댓값을 과학자의 h-index로 정의한다는 설명이 문제 지문에 제시되어 있다.

외국어로 작성된 문제 지문에 대한 해석 설명본은 아래 링크에 있으니, 문제 해결할 시 함께 참고하면 좋을 것이다.

https://www.acmicpc.net/board/view/105458

 

해당 문제에 대한 로직은, 아래의 사진과 함께 설명을 이어가는 것이 좋을 듯하다.

필자는, 각 논문의 인용 수치 값을 배열에 담았으며 이에 대하여 내림차순 정렬을 수행하도록 하였다.

그렇게 하여 연산을 진행하였는데, 고를 수 있는 논문의 총개수를 배열의 인덱스로 가정하여 정답을 탐색해 보았다.

요약해 보자면, 배열의 인덱스(고를 수 있는 논문의 개수)보다 배열값(인용 수치)이 크거나 같은 경우를 모두 카운팅 하여 이를 정답으로 출력하도록 하였다.

보다 자세한 설명은 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 논문의 개수(n)를 입력받는다.

 

2) 각 논문의 인용 수치를 저장할 벡터 h를 미리 선언해 둔다. (배열로 선언하여 활용하여도 좋다.)

 

3) n의 크기만큼, 반복문을 수행하여 n개 논문의 각 인용 수치(num)를 입력받도록 한다.

num을 하나씩 입력받는 대로, 각 값을 h의 요소로 삽입한다.

 

4) 입력값들이 들어있는 h에 대해, sort() 함수를 활용하여 정렬을 수행한다.

이때, sort()의 기본 정렬 방식은 오름차순이기 때문에, compare 함수를 별도로 선언하여 이를 통해 내림차순 정렬을 수행하도록 한다.

 

5) 정답을 저장할 변수 sum을 0으로 초기화하여 미리 선언해 둔다.

("sum값 이상의 인용 수치를 가진 논문을 sum개 고를 수 있다."의 최댓값을 찾아나갈 예정이다.)

 

6) n의 크기만큼, 반복문을 수행하여 아래의 연산을 취한다. 

- 현재 인덱스에 대한 배열값이 인덱스값보다 크거나 같다면, 이는 현재 인덱스의 값을 인용 수치로 가지는 논문을 현재 인덱스의 값만큼 고를 수 있음을 뜻한다. 따라서 이 경우에는, sum값에 1을 더하도록 한다.

- 다만 위 조건을 만족하지 않는다면, 고를 수 있는 논문을 더 이상 찾을 수 없기 때문에, 이 이상의 연산은 무의미하다고 볼 수 있다. 이 경우에는, 반복문을 탈출하여 연산을 종료하도록 한다.

 

7) 모든 연산이 완료되었다면, 최종적으로 저장된 sum 값을 정답으로 출력한 뒤 실행을 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 12109번 코드
bool compare(int a, int b) {
    return a > b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);   cout.tie(NULL);

    int n;
    cin >> n;

    vector<int> h;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;

        h.push_back(num);
    }
    sort(h.begin(), h.end(), compare);

    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (h[i] >= i + 1) { sum++; }
        else { break; }
    }
    cout << sum << endl;
}

 

제출 결과

(2025.06.30 백준 12109번 문제 제출 결과)

이번엔 설명이 난해한 감이 있다ㅠ