[프로그래머스/C++] 파일명 정렬

1.문제 링크

파일명 정렬

2. 풀이 전 계획과 생각

• 구현

3. 풀이

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool compare(pair<pair<string, string>, string> a, pair<pair<string, string>, string> b){
    string aHead = a.first.first;
    string bHead = b.first.first;
    for(int i=0;i<aHead.size();i++) aHead[i] = toupper(aHead[i]);
    for(int i=0;i<bHead.size();i++) bHead[i] = toupper(bHead[i]);
    int aNumber = stoi(a.first.second);
    int bNumber = stoi(b.first.second);
    if(aHead<bHead) return true;
    else if(aHead==bHead){
        if(aNumber<bNumber) return true;
        else return false;
    }
    else return false;
}

vector<string> solution(vector<string> files) {
    vector<pair<pair<string, string>, string>> v;
    for(int i=0;i<files.size();i++){
        string str = files[i];
        int startIndex=-1, endIndex=-1;
        for(int j=0;j<str.size();j++){
            if(startIndex==-1){
                if('0'<=str[j] && str[j]<='9'){
                    startIndex=j;
                }
            }
            else{
                if(!('0'<=str[j] && str[j]<='9')){
                    endIndex=j-1;
                }
            }
        }
        if(endIndex==-1) endIndex=str.size()-1;
        string head = str.substr(0, startIndex);
        string number;
        if(endIndex-startIndex+1>5){
            number = str.substr(startIndex, 5);
            endIndex = startIndex+4;
        }
        else{
            number = str.substr(startIndex, endIndex-startIndex+1);
        }

        string tail;
        if(endIndex==str.size()-1) tail = "";
        else{
            tail = str.substr(endIndex+1);
        }
        v.push_back({ {head,number}, tail});
    }

    stable_sort(v.begin(), v.end(), compare);

    vector<string> answer;
    for(int i=0;i<v.size();i++){
        string filename = v[i].first.first+v[i].first.second+v[i].second;
        answer.push_back(filename);
    }
    return answer;
}

주어진 조건으로 head, number, tail를 벡터에 삽입한다.

주어진 조건으로 compare 함수를 만든다.

stable_sort를 이용한다.

4. 풀이하면서 고민했던 점

• 정확도 테스트에서 1,2번을 제외하고 모드 오답처리됨 질문하기 게시판을 확인해보니 c++에서 sort 대신 stable_sort를 사용하면 해결된다고 해서 stable_sort를 사용하니 해결됨.

5. 문제를 풀고 알게된 개념 및 소감

• stable_sort에 대해 알게됨. 일반 sort는 퀵정렬을 이용하고, stable_sort는 합병정렬을 이용한다. 퀵정렬의 경우 만약 두쌍 이상을 정렬할 때 앞의 원소가 같은 경우 누가 앞에 올지 예측할 수 없다. 하지만 합병정렬의 경우 다르다. 그래서 두 개 이상원소를 가진 것들을 정렬할 때는 합병정렬로 구현된 stable_sort를 이용해야 한다.