[3차] 파일명 정렬

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool compare(pair<string,pair<string,int>> a, pair<string,pair<string,int>> b){
    /* HEAD 사전순 */
    if(a.second.first < b.second.first) return true;
    else if(a.second.first > b.second.first) return false;
    /* NUMBER 크기순 */
    if(a.second.second < b.second.second) return true;
    else if(a.second.second > b.second.second) return false;
    /* 둘 다 같다면 그냥 들어온 순 */
    return false;
}
vector<string> solution(vector<string> files) {
    vector<string> answer;
    /* first=원본, second.first=HEAD, second.second=NUMBER */
    vector<pair<string,pair<string,int>>> v;
    for(int i=0;i<files.size();i++)
    {
        int j=0;
        /* HEAD 추출 */
        string head = "";
        for(;j<files[i].length();j++)
        {
            char ch = files[i][j];
            if(ch >= '0' && ch <= '9') break;
            else head += ch;
        }
        /* NUMBER 추출 */
        string NUMBER = "";
        for(;j<files[i].length();j++)
        {
            char ch = files[i][j];
            if(ch >= '0' && ch <= '9') NUMBER += ch;
            else break;
        }
        /* 원본, head, Number를 삽입 */
        transform(head.begin(), head.end(), head.begin(), ::tolower);
        //cout << "files[i]="<<files[i]<<", head="<<head<<", number="<<NUMBER<<'\n';
        //if(NUMBER.length()>5) NUMBER = NUMBER.substr(0,5);
        v.push_back({files[i],{head, stoi(NUMBER)}});
    }
    stable_sort(v.begin(), v.end(), compare);
    for(int i=0;i<v.size();i++) answer.push_back(v[i].first);
    return answer;
}

• 아무리 생각해도 안되는게 이상해서 찾아봤더니 c++ STL의 sort는 불안정 정렬이라고 한다!!!!!

• <algorithm>'s sort()는 퀵정렬로 이루어져 있기 때문에 불안정함!
  (이유 : 퀵정렬은 같은 데이터를 비교할때 서로 바꿔주기 때문입니다. 문제는 같은 문자와 숫자일 경우에는 그대로 나둬야 하기 때문에 퀵정렬로 사용하면 에러가 발생)

• 같은 헤더에 존재하는 stable_sort()를 사용하면 문제가 해결된다!