[C++ STL] sort(first, last, comp) 함수 사용 방법 | 백준 1181번 단어 정렬

sort(first, last, comp) 함수란?

C++ STL의 algorithm 헤더에 정의된 정렬 함수를 의미한다.

 

sort 함수는 여러 가지 배열 또는 컨테이너의 시작(first)과 끝(last-1)의 범위를 지정하여 사용자가 원하는 정렬 기준(comp)에 따라  O(nlogn) time으로 정렬하는 함수를 말한다.

 

기본적으로, comp는 사용자 정의의 비교 함수를 의미하며 비교 함수를 생략한다면 기본적으로 오름차순으로 정렬되게 된다.

또한, 배열의 범위를 지정할 때 주의할 점은 인자로 first와 last를 넘겨주면, 실제로는 first부터 last-1까지만 정렬되게 된다.

 

정렬할 배열로는 내장 배열과 모든 컨테이너(ex:vector, list)가 가능하다.

 

sort 함수의 include 방법

#include <algorithm>

다음과 같이 algorithm 헤더를 include하면 사용할 수 있다.

여러 가지 정렬 방법 소개

여러 가지 정렬 방법 소개 전에, 아래 코드를 기준으로 설명하겠다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
    vector<string> array;
    array.push_back("D");
    array.push_back("A");
    array.push_back("E");
    array.push_back("C");
    array.push_back("B"); //D,A,E,C,B
    return 0;
}

정렬 방법 1 : 기본 정렬(default sorting) 은 오름차순 정렬이다.

sort 함수의 세번째 인자로 비교 함수를 생략한다면 기본적으로 오름차순으로 정렬하게 된다.

 

첫번째 인자와 두번째 인자는 해당 벡터의 시작주소와 끝 주소를 넘겨주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
    vector<string> array;
    array.push_back("D");
    array.push_back("A");
    array.push_back("E");
    array.push_back("C");
    array.push_back("B");

    //기본 정렬
    sort(array.begin(), array.end());
    for(string s : array) {
        cout << s << " "; //A B C D E
    }
    cout << endl;
    return 0;
}

정렬 방법 2 : 사용자 정의의 비교 함수로 내림차순 정렬

다음과 같이 사용자 정의의 비교 함수로 내림차순을 정의하였다.

 

두 개의 문자열을 입력 받아서 첫 번째 인자가 두 번째 인자보다 앞으로 올 조건으로 사전순으로 첫 번째 인자가 두 번째 인자보다 더 늦게 온다면 true를 리턴하고, 사전순으로 더 빠르다면 false를 리턴한다.

이때, false를 리턴 받으면 sort 함수는 두 인자의 자리를 바꿔서 정렬하게 된다.

 

또한, 비교 함수의 리턴 타입은 bool 타입으로 정의한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool comp(string a, string b) {
    return a > b;
}
int main(void) {
    vector<string> array;
    array.push_back("D");
    array.push_back("A");
    array.push_back("E");
    array.push_back("C");
    array.push_back("B");

    //사용자 정의의 비교 함수로 내림차순 정렬
    sort(array.begin(), array.end(), comp);
    for(string s : array) {
        cout << s << " "; //A B C D E
    }
    cout << endl;
    return 0;
}

---

sort 함수를 이용한 관련 백준 문제 | C++

1181번 단어 정렬

https://www.acmicpc.net/problem/1181

#include <iostream>
#include <unordered_set>
#include <algorithm>
#include <cstring>
using namespace std;
bool compare(string a, string b) {
    if(a.length() < b.length()) {
        return true;
    } else if (a.length() == b.length()) {
        if(strcmp(a.c_str(), b.c_str()) < 0) {
            return true;
        } else {
            return false;
        }
    } else {
        return false;
    }
}
int main(void) {
    //입력 수가 많으므로 비동기화 진행
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<string> array;
    unordered_set<string> keys;
    while(n--) {
        string userInput;
        cin >> userInput;
        //중복 확인 : O(1) time
        if(keys.find(userInput) == keys.end()) {
            //새로운 문자열 삽입 연산 : O(1) time
            keys.insert(userInput);
            array.push_back(userInput);
        }
    }
    //문자열 compare 함수 기준으로 정렬 : O(nlogn) time
    sort(array.begin(), array.end(), compare);
    //printf 사용
    for(string element : array){
        printf("%s\n", element.c_str());
    }
    return 0;
}

위 코드의 비교 함수를 살펴보도록 하자.

 

문제 조건에 맞게, 먼저 두 문자열의 길이를 비교하고, 두 문자열의 길이가 같다면 사전순으로 먼저 오는 문자열을 확인한다.

 

문제 조건에 모두 만족하는 두 문자열이면 비교 함수는 true를 리턴하여, swap을 진행하지 않고 그대로 정렬한다.

반면, 문제 조건에 만족하지 않는 두 문자열이면 비교 함수는 false를 리턴하여, swap을 진행하고 정렬한다.

---

추가로 sort 함수와 관련하여 궁금한 점은

https://cplusplus.com/reference/algorithm/sort/?kw=sort

https://cplusplus.com/reference/algorithm/sort/?kw=sort

위 사이트를 참고하도록 하자.