#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){
if(a.second.first < b.second.first) return true;
else if(a.second.first > b.second.first) return false;
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;
vector<pair<string,pair<string,int>>> v;
for(int i=0;i<files.size();i++)
{
int j=0;
string head = "";
for(;j<files[i].length();j++)
{
char ch = files[i][j];
if(ch >= '0' && ch <= '9') break;
else head += ch;
}
string NUMBER = "";
for(;j<files[i].length();j++)
{
char ch = files[i][j];
if(ch >= '0' && ch <= '9') NUMBER += ch;
else break;
}
transform(head.begin(), head.end(), head.begin(), ::tolower);
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()
를 사용하면 문제가 해결된다!