web/알고리즘

프로그래머스 알고리즘 고득점 Kit - 정렬

민사민서 2024. 2. 17. 00:04

C++ 벡터 복사

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    vector<int> temp;

    for(int i = 0; i < commands.size(); i++) {
        temp = array;

- 이렇게 할당 연산자 = 을 사용하면 deep copy 된다

vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    
    for(vector<int> command : commands) {
        vector<int> tmp(array.begin()+command[0]-1, array.begin()+command[1]);

- 나는 이렇게 범위 생성자를 사용했다. 대신 종료 iterator는 마지막 원소 + 1로 주어야 함

 

C++ 벡터 정렬

sort(temp.begin() + commands[i][0] - 1, temp.begin() + commands[i][1]);

- 마찬가지로 범위 지정 가능, 대신 종료 iterator는 마지막 원소의 다음 위치로 주어야 

 

가장 큰 수

- 정렬 시 const string& a 이런 식으로 넘겨주면 copy construct되지 않아 메모리를 효율적으로 쓴다고 함

bool comp(const string& s1, const string& s2) {
    return stoi(s1+s2) > stoi(s2+s1);
}
string solution(vector<int> numbers) {
    vector<string> nums;
    for(int n : numbers) {
        nums.push_back(to_string(n));
    }
    sort(nums.begin(), nums.end(), comp);

 

H-index

- 논문 n편 중, h번 이상 인용된 논문이 h편 이상인 h의 최댓값이 h-index 라고 함

- 내림차순 정렬은 sort(citations.begin(), citations.end(), greater<int>()) 하면 됨

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

using namespace std;

int solution(vector<int> citations) {
    sort(citations.begin(), citations.end(), greater<int>());
    
    int N = citations.size();
    int answer = N;
    while(answer>0) {
        if(citations[answer-1] >= answer) break;
        answer--;
    }
    
    return answer;
}

// 내림차순 정렬해두고, 최댓값 H를 구하기 위해 h를 N부터 1씩 감소시켜가며 조건 만족하는지 봄

// [0,0,0,0 ..] 일 때도 결국 0 반환