Sort 함수의 커스터마이징, 특정 조건 정렬

알고리즘 문제를 풀다보면 Algorithm 헤더에 포함된 Sort 함수를 자주 이용합니다.

기본적으로 디폴트 함수를 이용해 오름차순 정렬을 이용합니다.

#include <iostream>
#include <algorithm>
using namespace std;

void main(){
	int arr[10] = { 2,8,4,6,7,5,1,3,10,9 };
	sort(arr, arr + 10);
	for (int i = 0; i < 10; i++) {
		cout << arr[i] << " ";
	}
}

 

다만 해당 Sort 함수는 세번째 파라미터에 비교하는 함수를 추가해 오름차순 이외에도 특정 조건 정렬을 실행할 수도 있습니다. 이번에 Sort함수에 함수를 추가해 이용해보게된 계기는 프로그래머스의 '가장 큰 수' 문제입니다.

 

https://programmers.co.kr/learn/courses/30/lessons/42746

코딩테스트 연습 - 가장 큰 수

 

풀이과정 중에 두 문자열을 비교해서 '앞자리'가 더 큰 수를 앞에 두도록 정렬하는 과정이 필요했는데

이를 해결하기위해 별도의 비교함수(cmp)를 작성하고 Sort함수의 세번째 파라미터로 이용하였습니다.

 

int cmp(string &a,string &b){
    return a+b>b+a;
}


string solution(vector<int> numbers) {
    string answer = "";
    
    vector<string>snum;
    for(int i=0;i<numbers.size();i++){
        string str = to_string(numbers[i]);
        snum.push_back(str);
    }
    sort(snum.begin(),snum.end(),cmp);
    
    for(int i=0;i<snum.size();i++){
        answer +=snum[i];
    }

 

Algorithm헤더로 이용할 수 있는 Sort함수는 intro sort라는 알고리즘으로 작성되어 있다고 합니다.intro sort는 세 가지 정렬법(quick sort, heap sort, insertion sort)을 섞어 quick sort의 단점을 보완하여 어떤 상황에서도 O(nlogn)의 시간 복잡도를 가질 수 있는 정렬법입니다.

 

일반적으로 quick sort의 풀이과정으로 sort 함수를 가정하자 특수 조건을 작성하기 쉬웠습니다.

비교함수의 파라미터 변수 a,b 에 두 값이 순서가 바뀌어서 들어왔을 때도, 0,0이 들어왔을때도(예외사항) 일관된 리턴값을 낼 수 있어야 합니다.  '가장 큰 수' 문제의 풀이법은 위와 같이 더 큰 수를 만들수 있게끔 a를 앞에 두고 문자열을 합쳤을때만 true를 반환하게끔 작성하였습니다.

 

이외에도 홀수,짝수를 구분해 홀수에 우선순위를 코드도 작성할 수 있습니다.

#include <algorithm>
#include <iostream>
using namespace std;
int arr[10] = { 2,8,4,6,7,5,1,3,10,9 };
int cmp(int a, int b) {
	if (a % 2 && b % 2) { // 둘다 홀수
		return a < b;
	}
	else if (a % 2) { // a만 홀수
		return 1;
	}
	else if (b % 2) { // b만 홀수
		return 0;
	}
	return a < b; // 둘다 짝수
}

 

별도의 비교함수로 sort함수를 커스터마이징할때 비교문에서 예외사항이 발생하면 Sort함수 실행중 오류가 발생하니 if문을 통해 별도의 예외사항을 세심히 처리해야합니다.