[정렬] K번째 수, 가장 큰 수, H-Index, 수 정렬하기, 나이순 정렬, 단어 정렬

K번째 수

< 문제 >

알고리즘 이미지

splice를 통해 배열을 자르고 새로운 배열에 추가한다.

이후에 정렬을 하고 N번째 값을 리턴한다.

문제 따라서 해결 하면 되는 문제이다.

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
vector<int> solution(vector<int> array, vector<vector<int>> commands) {
    vector<int> answer;
    vector<int> tempArr;
    for(vector<int> arr : commands) {
        tempArr.clear();
        
        tempArr.assign(array.begin() + arr[0] - 1 , array.begin() + arr[1]); //splice
        sort(tempArr.begin(),tempArr.end());
        
        answer.push_back(tempArr[arr[2]-1]);
    }
    
    return answer;
}

< 소스 코드 >

가장 큰 수

< 문제 >  

알고리즘 이미지

숫자를 정렬할 때 값을 문자열로 보고 정렬하여 문제를 해결하는 경우

두 문자열의 합을 비교하여 더 큰 값 순서대로 정렬

이 때, 중복은 허용하지 않는다 (000과 같은 경우 0을 리턴)

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool compare(int preNum, int postNum) {
    string pre = to_string(preNum);
    string post = to_string(postNum);
    string compxFirst = pre + post;
    string compxSecond = post + pre;
    if(compxFirst > compxSecond) {
        return true;
    }
    return false;
}
 
string solution(vector<int> numbers) {
    string answer = "";
    sort(numbers.begin(),numbers.end(),compare);
    
    if(numbers[0] == 0) {
        return "0";
    }
 
    for(int i : numbers) {
        string str =  to_string(i);
        answer = answer + str;
    }
    return answer;
}

< 소스 코드 >

H-Index

< 문제 >

알고리즘 이미지

아이디어 문제

내림차순 정렬 후에 인덱스보다 값이 더 작을 때의 값을 리턴한다.

 

#include <string>
#include <vector>
#include <algorithm> 
 
using namespace std;
 
int solution(vector<int> citations) {
    int answer = 0;
    sort(citations.rbegin(),citations.rend());
    for(int i=0; i<citations.size(); i++) {
        if(citations[i] <= i) {
            return answer;
        }
        answer++;
    }
    return answer;
}

< 소스 코드 >

 

수 정렬하기 3

< 문제 >

실제로 정렬하지 않고 인덱스를 이용해서 값을 출력하는 문제

 

#include<stdio.h>
 
int cnt[10001];
int main()
{
    int n;
    int v=0;
    scanf("%d",&n);
 
    for(int i=0; i<n; i++)
    {
        scanf("%d",&v);
        cnt[v]++;
    }
    
    for(int i=1; i<=10000; i++)
    {
        if(cnt[i] >0)
            for(int j=0; j<cnt[i]; j++)
                printf("%d\n",i);
    }
 
 
    return 0;
}
 
 

< 소스코드 >

 

나이순 정렬

< 문제 >

C++의 구조체와 람다식을 이해할 수 있는 문제

또한 벡터의 구조체를 다루는 법에 대해서 알수 있다.

 

 

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Person { //구조체의 형식
    int age;
    string name;
    int join;
};
int main() {
    int n;
    cin >> n;
    vector<Person> a(n);
    for (int i=0; i<n; i++) {
        cin >> a[i].age >> a[i].name; //벡터에 Person인스턴스를 생성하지 않고 입력한다!
        a[i].join = i;
    }
 
    sort(a.begin(), a.end(), [](Person u, Person v) {
        return (u.age < v.age) || (u.age == v.age && u.join < v.join);
    });
 
    for(auto p : a) { //auto는 제너레이터가 작동하듯 타입을 알아서 판단한다.
// p의 Person객체 대신 auto를 사용해주었다.
        cout << p.age << ' ' << p.name << '\n';
    }
    return 0;
}

< 소스코드 >

 

단어 정렬

핵심은

정렬 된 값들은 중복 제거를 위해서

temp값이 이전 값만 기억해두고 있으면 된다는 점!

 

#include <bits/stdc++.h>
 
using namespace std;
 
bool compare(string a, string b){
    if(a.length() == b.length()){
        return a<b;
    }
    return a.length() < b.length();
}
 
int main()
{
    int n ;
    cin >> n;
    string word[n];
    for(int i =0; i<n; i++) {
        cin>>word[i];
    }
    
    sort(word,word+n,compare);
    
    string checker = ""; // 중복을 위해 임시로 기억해두기 위한 변수
    
    for(int i =0; i<n; i++) {
        if(checker != word[i]){ 중복에 대한 처리를 한다!
        cout << word[i];
        cout << "\n";
        }
        checker = word[i]; // 임시로 기억했다가! ↑
        
    }
    
    return 0;
}