프로그래머스/H-Index(정렬)/C++ ; 정렬 없이 풀기, 정렬하여 풀기

 

즉, citations 배열에서 h 이상의 값을 가지는 원소가 h개 이상인 h의 최대값을 찾는 것이다. 문제 설명이 다소 혼란스러워서 문제 자체를 이해하는 데에 어려움을 겪는 사람이 많아보였다. 나도 문제를 읽으면 읽을수록 헷갈렸기에, 주의할 점과 테스트 케이스를 자세히 적어보았다.

 

주의해야 할 점

1. h가 반드시 citations 배열의 원소값이어야 하는 것은 아니다.

    -> citations = [10, 9, 4, 1, 1], answer = 3

 

2. h 이상의 값을 가지는 원소가 h개여야 하는 것은 아니다.

    -> citations = [0, 1, 1], answer = 1

 

3. h 값은 citations 배열의 size 값보다 큰 값일 수 없다.

    -> citations = [31,66], answer = 2 

 

 

위와 같은 주의점을 상기하여 코드를 짠다면 통과할 수 있을 것이다.

 

 

 

첫 번째 코드 : 정렬 없이 풀기 1

 

정렬 부분의 문제이긴 하나, 반드시 정렬을 사용해야 풀 수 있는 문제인 건 아니다. 아래의 방법은 정렬을 사용하는 것보다 시간이 오래 걸리긴 한다. ( 평균 약 0.5ms 정도)

 

answer 값은 citations 배열의 size보다 클 수 없기 때문에 변수 i를 사용하는 for문의 범위를 저렇게 설정해줘도 된다. (i<citations.size()).

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;

    bool ended[citations.size()]; // 더 이상 비교해보지 않아도 된다면 true, 아니라면 false
    fill_n(ended, citations.size(), false);

    for (int i = 0; i < citations.size(); i++) {
        int v = 0;
        for (int j = 0; j < citations.size(); j++) {
            if (!ended[j]) { // 비교해봐야 하는 원소인 경우
                if (citations[j] >= i) v++; // i값 이상의 원소 개수 count
                else ended[j] = true; // i값보다 작은 경우 i+1부터는 방문하지 않도록 함.
            }
        }

        if (v >= i) // i값 이상의 원소 개수(v)가 i개 이상이라면
            answer = i;
    }

    return answer;
}

 

디버깅 기록

1. 처음에는 max_citaion을 구하여 그 크기까지 돌렸더니, 정렬하고 푸는 코드와 시간 차이가 매우 크게 났었다. 어차피 anser는 citations의 크기보다 클 수 없다는 것을 아는 것이 중요하다.

 

2. bool 배열을 정의할 때, vector의 사이즈값을 받아와서 개수를 설정하면 bool 배열을 정의하면서 한 번에 초기화시키는 게 안 된다. (bool ended[citations.size()] = {false}가 오류가 난다는 뜻) 그래서 초기화를 안 하고 썼다가 오류 파티에 봉착하였는데, fill_n 함수를 써서 초기화를 하니 제대로 된 값이 나왔다. 어제 월코챌2 3번에서도 같은 방법을 썼었는데 그때는 fill_n으로 따로 bool 배열을 초기화하지 않아서 오류난 건 아닌가 싶다.

 

3. i를 작은 순서대로 구했기 때문에 ended 배열을 사용하여 연산을 줄일 수 있었고, answer값을 갱신할 때도 추가적으로 비교할 필요가 없었다. (어차피 뒤에 오는 i값이 더 크니까) 하지만! i를 큰 것부터 한다면 연산이 훨씬 줄어든다. 해당 코드는 아래와 같다.

 

 

 

 

 

두 번째 코드 : 정렬 없이 풀기 2

 

첫 번째 코드와 비교하여 다른 점은, (1) 변수 i를 사용하는 for문이 역순이라는 것, (2) 그래서 ended 배열을 쓸 수 없다는 것 (i+1보다 작다고 해서 i보다 작은 것은 아니기 때문에) (3) 그 덕분에 v보다 크거나 같은 i를 구하자마자 그 값을 리턴시킬 수 있다는 것.

 

아래의 코드는 정렬하여 푸는 방법과 시간 차이가 거의 나지 않는다. 어떤 케이스에서는 정렬하여 푸는 것이 조금 더 오래 걸렸다. 아래의 코드는 모든 테스트 케이스를 0.02ms 내에서 완료하였다.

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;

    for (int i = citations.size(); i >= 0; i--) {
        int v = 0;
        for (int j = 0; j < citations.size(); j++) {
            if (citations[j] >= i) v++;
        }

        if (v >= i) {
            return i;
        }
    }

    return answer;
}

 

이건 기존의 코드를 주의할 점을 어기지 않는 내에서 발전시킨 것이라 별도의 디버깅 과정이 없었다.

 

 

 

 

 

세 번째 코드 : 정렬하여 풀기

 

정렬 문제라는 것을 의식하고 있었다면, 나도 처음부터 이 방법만을 떠올리고 이 방법 밖에 쓰지 못했을 것이다. 많은 사람들이 정렬을 사용하여 풀었기에 정렬 없이 푸는 방법을 먼저 소개했다. 다른 사람들의 코드를 보고 작성한 것이라 온전히 내 힘만으로 쓴 것은 아니지만, 내가 정렬로 푸려고 했다면 아마 이 방법을 시도했을 것 같아 소개한다.

 

문제 조건에서 주고 있는 힌트를 활용하면 된다. h번 이상 인용된 논문이 h편 이상이라면, 나머지 논문은 h번 이하 인용되었다는 것. 즉, h 이상의 값을 가지는 원소가 h개 이상이라면 나머지 원소들은 h 미만의 값이 아니라 h 이하의 값을 가질 것이다. 문제는 이 등호에 있는 것이다.

 

#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();
}

 

디버깅 기록

1. for문 안의 if문을 처음에는 citations[i] <= (i+1)로 설정하였다. 리턴값을 citations[i], i, i+1로 열심히 수정해봤지만 계속 오류가 났다. 리턴값을 i로 하니 index가 0부터 시작하여 옳은 값보다 1이 작은 값이 나왔고, citations[i]로 하니 위에서 적은 주의할 점에 위배되었다. (h값이 반드시 citations 배열의 원소값이어야 하는 것은 아니다.)

 

이미 문제를 푼 상태였기 때문에 다른 사람의 코드를 볼 수 있어서, 다른 사람의 코드를 참고하여서 if문의 조건에서 등호를 뺐다. 먼저 고치고 나니까 머리로 이해가 됐다. citations[i] < i+1이라는 것은, citations[i]를 포함한 그 이후의 원소들은 i보다 작거나 같다는 것을 보장해주고, citations[i] 이전의 원소들은 i보다 크거나 같다는 것을 보장해주었다. (이전 단계에서 if문을 만족시키지 않았으므로)

 

문제에서 주는 조건을 가장한 힌트를 잘 파악하여 이용하는 것도 중요하다는 것을 느꼈다.