[프로그래머스] 코딩테스트 고득점 Kit 정렬 C++ (K번째 수, 가장 큰 수, H-Index)

 

1️⃣ K번째수

프로그래머스

 

• 생각 흐름
  • 인덱스만큼만 새로운 벡터에 저장하고 sort하고 k번째 수 찾아서 answer에 넣기

코드

// 241024 23:50 시작 11:59 끝

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

using namespace std;

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    
    for (auto command: commands){
        vector<int> v;
        for (int i=command[0]-1;i<=command[1]-1;i++){
            v.push_back(array[i]);
        }
        sort(v.begin(), v.end());
        answer.push_back(v[command[2]-1]);
    }
    
    return answer;
}

 

vector<int> v를 갱신해주지 않아서 틀린 답이 나왔었다. 그래서 for문 안에 선언을 해줬더니 정답을 맞출 수 있었다. 위에 생각 흐름에 적은 것을 문제를 읽자마자 생각했고, 코드를 빠르게 작성할 수 있었다.

---

 

2️⃣ 가장 큰 수

프로그래머스

 

• 생각 흐름
  • sort만 하면 10이 6보다 큰 걸로 인식되는데,,
  • compare 함수 이용해서 10으로 나눈 나머지가 10미만일때까지 나누고, 나눈 몫이 아니다 복잡해
  • numbers의 원소를 string으로 바꾸고 두 문자열을 합쳤을 때 큰거대로 저장하기

코드

// 241025 00:04 시작 00:18 끝

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

using namespace std;

bool compare(string a, string b){
    return a+b > b+a;
}

string solution(vector<int> numbers) {
    string answer = "";
    
    vector <string> v;
    for (int number: numbers){
        v.push_back(to_string(number));
    }
    sort(v.begin(), v.end(), compare);
    
    if (v[0]=="0") return "0";
    
    for (int i=0;i<v.size();i++){
        answer += v[i];
    }
    
    return answer;
}

 

이 문제 풀면서 고민했던건 아이디어다. integer로 계속 원소의 자료형을 가져가면 복잡해지기 때문에 string으로 바꿀 생각을 하게 됐고, string으로 바꾼다면 앞 숫자가 클수록 크다고 인식하기 때문에 아이디어 생각까지만 하면 수월하게 풀 수 있는 문제다.

 

---

3️⃣ H-Index

프로그래머스

 

• 생각 흐름
  • 주어진 배열 정렬하고 
  • citations[i]를 사용해서 h 구하면 되겠다!

코드1 - 오답

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

using namespace std;

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

 

와장창 틀렸다... 

논문 n편 중, h번 이상 인용된 논문이 h편 이상이고, 나머지는 h번 이하 인용되었다면 h의 최댓값이 과학자의 h-index다.

앞에서부터 벡터를 탐색하고 있으니까 citations.size()-i는 현재 탐색하고 있는 원소 + 아직 탐색하지 않은 원소들의 개수일테고, 최댓값을 구하는거니까 answer를 갱신해주면 된다고 생각했다.

근데 우선 부등호부터 잘못됐다. citations[i] 이상 인용되어야 하는거니까 n-i이 citations[i]보다 크거나 같아야 하고, 크거나 같은게 처음 나오면 i번째에서 h-index가 가장 큰 것이고, citations[i]가 아니라 n-i가 리턴되어야 한다.

그 이유는 h-index의 정의와 관련이 있는데, h-index는 연구자의 논문 중 h번 이상 인용된 논문이 h편 이상이고, 나머지는 h번 이하 인용된 경우의 최대 h값이다. 즉, '몇 편의 논문이 h번 이상 인용되었는가'가 중요하지, 개별 논문의 인용 횟수가 중요한게 아니다. citations[i]를 반환하면 개별 논문의 인용 횟수를 반환하게 되는 것이다. 그래서 탐색하고 있는 시점에서 남은 논문들의 수를 나타내는 n-i를 반환하는 것이 옳다.

 

 

코드2 - 정답

// 241025 00:24 시작 00:44 끝

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

using namespace std;

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

 

위에서 정리한 내용대로 코드를 작성하니 테스트 케이스를 모두 통과할 수 있었다.