Programers : [3차] 파일명 정렬(stable_sort)
12778 단어 level2PROGRAMERSPROGRAMERS
[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()
를 사용하면 문제가 해결된다!
Author And Source
이 문제에 관하여(Programers : [3차] 파일명 정렬(stable_sort)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@neity16/Programers-3차-파일명-정렬stablesort
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
#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()
를 사용하면 문제가 해결된다!
Author And Source
이 문제에 관하여(Programers : [3차] 파일명 정렬(stable_sort)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@neity16/Programers-3차-파일명-정렬stablesort저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)