정렬

일반적인 정렬

일반적인 정렬은 다음과 같이 std::sort를 쓰면 손쉽게 가능하다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int arr[7] = {5,3,67,21,67,2,69};
    sort(arr, arr+7);
    for(int i=0;i<7;i++) printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

실행 결과는 다음과 같다.

$ ./a.out
2 3 5 21 67 67 69

 

비교함수 제작을 통한 커스텀 정렬 구현하기

주의 할점

1. 두 원소가 같을때 true를 리턴하지 않도록 주의(항상 return a>b; 또는 return a<b; 형태로 등호를 포함하지 않도록 리턴하자)

2. 매개변수를 받을때 &를 붙여서 불필요한 복사가 일어나지 않도록 하자.

아래는 커스텀 비교함수의 예시이다. 이 문제의 답이기도 하다.

#include <bits/stdc++.h>
using namespace std;
map<string, int> cnt;
bool compare(string& a, string& b) {
    if(cnt[a]!=cnt[b]){
        return cnt[a]>cnt[b];  // 출현빈도 기준 내림차순
    }
    if(a.length() != b.length()){
        return a.length()>b.length();  // 단어 길이에 따른 내림차순
    }
    return a < b;  // 사전순 오름차순
}
int main() {
    int N, M; scanf("%d%d\n", &N, &M);
    vector<string> v;
    while(N--) {
        char word[11];scanf("%s\n", word);
        if(strlen(word)<M) continue;
        cnt[word]++;
        if(cnt[word]==1) v.push_back(word);
    }
    sort(v.begin(), v.end(), compare);
    for(auto e:v) printf("%s\n", e.c_str());
    return 0;
}

아래처럼 람다함수를 써도 된다.

#include <bits/stdc++.h>
using namespace std;
map<string, int> cnt;
int main() {
    int N, M; scanf("%d%d\n", &N, &M);
    vector<string> v;
    while(N--) {
        char word[11];scanf("%s\n", word);
        if(strlen(word)<M) continue;
        cnt[word]++;
        if(cnt[word]==1) v.push_back(word);
    }
    sort(v.begin(), v.end(), [&](string& a, string& b){
        if(cnt[a]!=cnt[b]){
            return cnt[a]>cnt[b];  // 출현빈도 기준 내림차순
        }
        if(a.length() != b.length()){
            return a.length()>b.length();  // 단어 길이에 따른 내림차순
        }
        return a < b;  // 사전순
    });
    for(auto e:v) printf("%s\n", e.c_str());
    return 0;
}