프로그래머스 - [3차] 파일명 정렬

프로그래머스 - [3차] 파일명 정렬

처음에 sort써서 틀렸다가 stable_sort로 바꾸고, stable_sort가 상대적 위치를 변경하지 않는다는 것을 확인하고, files별로 idx를 sort 기준에 추가해서 sort로 바꿨다.
stable_sort는 O((NlogN^2))로 시간복잡도가 높다.

코드는 다음과 같다.

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

using namespace std;

typedef struct __info {
    string head;
    int num;
    int idx;
    string file;
} info;

bool comp(const info &a, const info &b)
{
    if(a.head == b.head) {
        if(a.num == b.num)
            return a.idx < b.idx;
        return a.num < b.num;
    }
    return a.head < b.head;
}

vector<string> solution(vector<string> files) {
    vector<string> answer;
    vector<info> v1;
    
    for(int i=0;i<files.size();i++) {
        int start = 0;
        for(int j=0;j<files[i].size();j++) {
            if(!isdigit(files[i][j])) 
                continue;
            start = j;
            break;
        }
        string head = files[i].substr(0, start);
        transform(head.begin(), head.end(), head.begin(), ::tolower);
        
        int end = files[i].size();
        for(int j=start;j<files[i].size();j++) {
            if(isdigit(files[i][j]))
                continue;
            end = j;
            break;
        }
        string num = files[i].substr(start, end);
        
        v1.push_back({head, stoi(num), i, files[i]});
    }
    
    sort(v1.begin(), v1.end(), comp);

    for(auto it : v1) 
        answer.push_back(it.file);
    
    return answer;
}