[c++] 프로그래머스 - [3차] 파일명 정렬(Level 2)

문제

코딩테스트 연습 - [3차] 파일명 정렬

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

//22:13 ~ 22:50
using namespace std;
struct Detail{
    string head;
    int num;
    string origin;
};
vector<string> answer;
bool cmp(const Detail& d1, const Detail& d2){
    if(d1.head!=d2.head) return d1.head<d2.head;
    else if(d1.num!=d2.num) return d1.num<d2.num;
    return false;
}

Detail divide(string s){
    string head,num,temp;
    Detail detail;
    
    for(int i=0; i<s.length(); i++){
        if(!isdigit(s[i])&&num.empty()) temp+=s[i];
        else{
            if(head.empty()){
                head = temp;
                temp.clear();
                num+=s[i];
            }
            else num+=s[i];
        }
    }
    
    detail.head = head;
    detail.num = stoi(num);
    detail.origin = s;
    return detail;
}
vector<string> solution(vector<string> files) {
    vector<Detail> v;
    
    for(string file:files) v.push_back(divide(file));
    
    for(int i=0; i<v.size(); i++) transform(v[i].head.begin(), v[i].head.end(), v[i].head.begin(),::tolower);
    
    stable_sort(v.begin(),v.end(),cmp);	// 여기 그냥 sort하면 틀림!!
    
    for(int i=0; i<v.size(); i++) answer.push_back(v[i].origin);
    
    return answer;
}

int main(){
    solution({"O00321", "O49qcGPHuRLR5FEfoO00321"});
    for(int i=0; i<answer.size(); i++){
        cout<<answer[i]<<'\n';
    }
}

 

풀이(37분)

이 문제를 통해서 c++의 stable_sort와 sort의 차이에 대해서 알게 되었습니다. 분명 완벽하게 구현했는데 계속 오답이 뜨길래 질문 목록을 찾아보니 c++을 사용하는 사람은 sort를 stable_sort로 바꿔주면 해결이 된다고 해서 바꿨는데 바로 정답이 떴습니다.

sort와 stable_sort

일반적으로 속도 같은 경우는 sort가 더 빠르지만 동일한 우선순위에 한해서는 순서를 보장하지 않는다고 합니다. 반면에 stable_sort는 동일한 우선순위일 때 순서를 보장해준다고 합니다.