프로그래머스 42747 - H-Index

오답1 (12.5 / 100)

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

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    
    // n: citations.size() - 논문 개수
    // h: 각 논문 인용 횟수
    // H-Index: i를 기준으로 end까지 자른 배열의 크기 >= vector[i] && begin부터 i - 1까지 자른 배열의 각 원소가 vector[i] 이하
    // - H-Index를 구할 때 최대값으로 갱신
    // - h를 기준으로 자른 배열의 크기가 h보다 작으면 종료
    
    sort(citations.begin(), citations.end());
    
    for (int i = 0; i < citations.size(); i++) {
        int h = 0;
        vector<int> tmp(citations.begin() + i, citations.end());
        vector<int> rest(citations.begin(), citations.begin() + i);
        
        if (tmp.size() >= citations[i]) {
            h = citations[i];
        }
        
        if (h > answer) answer = h;
    }
    
    return answer;
}

💥 문제점

• h번 이상 인용된 논문이 h개 이상이면 H-index는 h라고 했으니까
  [10]일 때, 10번 이상 인용된 논문이 10개 이상이어야 H-index = 10이 성립하는데, 한 개의 논문이 10번 인용되었지만 논문 개수가 10개가 아니니까 H-index = 10 자체가 성립이 안 돼서 H-index = 0으로 도출되는 줄 앎
  즉, H-index를 0부터 h까지 1씩 증가시키면서 판단하는 건데, 그냥 논문의 횟수 (citations의 각 원소 자체)를 h로 일단 놓고 판단하는 줄 알았음

오답2 (93.8 / 100)

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

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    
    sort(citations.begin(), citations.end());
    
    for (int h = 0; h < citations.size(); h++) {
        // citations 중에서 h 이상인 원소의 index 찾기
        int index = -1;
        for (int i = 0; i < citations.size(); i++) {
            if (citations[i] >= h) {
                index = i;
                break;
            }
        }
        
        // index가 -1이면 h 이상인 원소가 없다는 것
        // index를 찾았으면 해당 원소부터 끝까지 잘라낸 배열의 크기가 h 이상인지 비교
        if (index != -1) {
            vector<int> tmp(citations.begin() + index, citations.end());
            if (tmp.size() >= h) // h 이상이면 H-index는 h
                answer = h;
        }
    }
    
    return answer;
}

풀이

• 논문 n개 중, h번 이상 인용된 논문이 h편 이상이어야 H-index = h 성립
• 최대 h는 citations의 크기
  → h 이상인 논문이 h개 이상 존재해야 하기 때문
  ex) [5, 5, 5, 5]일 때, 인용횟수가 5이더라도 논문의 개수가 4개이기 때문에 최대 H-Index는 4

💥 문제점

h의 최대는 citations의 크기이기 때문에 h가 citations.size() 이상일 때도 포함해서 반복을 해야하는데 반복문의 조건 설정 잘못 함

✅ 해결

반복문 조건 h <= citations.size()로 수정

정답

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

using namespace std;

int solution(vector<int> citations) {
    int answer = 0;
    
    sort(citations.begin(), citations.end());
    
    for (int h = 0; h <= citations.size(); h++) {
        // citations 중에서 h 이상인 원소의 index 찾기
        int index = -1;
        for (int i = 0; i < citations.size(); i++) {
            if (citations[i] >= h) {
                index = i;
                break;
            }
        }
        
        // index가 -1이면 h 이상인 원소가 없다는 것
        // index를 찾았으면 해당 원소부터 끝까지 잘라낸 배열의 크기가 h 이상인지 비교
        if (index != -1) {
            vector<int> tmp(citations.begin() + index, citations.end());
            if (tmp.size() >= h) // h 이상이면 H-index는 h
                answer = h;
        }
    }
    
    return answer;
}

---

백준 10988 - 팰린드롬인지 확인하기

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

using namespace std;
    
int main() {
    string s;    
    cin >> s;

    string reverse_s(s.rbegin(), s.rend());

    if (s == reverse_s) cout << 1;
    else cout << 0;
    
    return 0;
}

💡

• reverse(): 원본 문자열을 반대로 뒤집음 → O(N)
• reverse_s(s.rbegin(), s.rend()): 원본문자열의 끝부터 시작까지 새로운 문자열에 할당
  • s.rbegin(): 문자열 s의 끝부터 시작하는 역반복자(reverse iterator)
  • s.rend(): 문자열 s의 시작 전을 가리키는 역반복자