[알고리즘C++] [3차]파일명 정렬

오늘의 문제

https://programmers.co.kr/learn/courses/30/lessons/17686

파일명 정렬

나의 풀이

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

using namespace std;

vector<string> spl(string name){
    transform(name.begin(), name.end(), name.begin(), ::tolower);
    vector<string> ret;
    bool check = false;
    int number;
    for(int i=0;i<name.size();i++){
        if(name[i] >= '0' && name[i] <= '9'){
            if(check == false){
                ret.push_back(name.substr(0, i));
                number = i;
                check = true;
            }else{
                if(i-number+1 == 5 ){
                    ret.push_back(name.substr(number, 5));
                    return ret;
                }
            }
        }else{
            if(check == true){
                ret.push_back(name.substr(number, i-number));
                return ret;
            }
        }
    }
    ret.push_back(name.substr(number, name.size()-number));
    return ret;
}

bool cmp(string a, string b){
    
    vector<string>split= spl(a);
    string head = split[0];
    int num = stoi(split[1]);
    
    vector<string>split2= spl(b);
    string head2 = split2[0];
    int num2 = stoi(split2[1]);
    if(head <  head2)
        return true;
    else if(head >= head2){
        if(head == head2){
            if(num < num2)
                return true;
            else if(num >= num2)
                return false; } 
        return false; 
    }
}

vector<string> solution(vector<string> files) {
    stable_sort(files.begin(), files.end(), cmp);
    return files;
}

모범 답안

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cctype>
using namespace std;
char makeLower(char c)
{
    if (c >= 'A' && c <= 'Z') c += 'a' - 'A';
    return c;
}
int findNumIdx(const string &str)
{
    int i;
    for (i = 0; i < str.length(); i++)
    {
        if (str[i] >= '0' && str[i] <= '9')
            break;
    }
    return i;
}
int getNumber(string str)
{
    return std::stoi(str.substr( findNumIdx(str) ));
}
string getHeader(string str)
{
    string rtn = str.substr(0, findNumIdx(str));

    std::transform(rtn.begin(), rtn.end(), rtn.begin(), makeLower);

    return rtn;
}

bool numComp(string str1, string str2) { return getNumber(str1) < getNumber(str2); }
bool headComp(string str1, string str2) { return getHeader(str1).compare(getHeader(str2)) < 0; }

vector<string> solution(vector<string> files)
{   
    std::stable_sort(files.begin(), files.end(), numComp);

    std::stable_sort(files.begin(), files.end(), headComp);

    return files;
}

배울 점

• 진짜 이거야말로 코테에서 아 개쉽네 하고 넘겼다가 실패할 문제다..

• STL의 sort가 불안정한 퀵 소트 기반 알고리즘이라는 걸 처음 알았다.. 해결방법은 너무나 간단하게도 stable_sort함수를 사용하는 것.. wow..

  	정렬 알고리즘에서 인덱스가 변경되는 알고리즘은 unstable하다(selection, quick, heap sort)
  	특히 각 문자가 같은 경우, 무엇이 앞에 오게 될 지 예측할 수 없음
  	불안정하지 않은 정렬 알고리즘: merge, buble, insertion sort

• compare함수를 사용하여 푸는 연습을 할 수 있어서 좋았다.
• 모범정답을 보면 compare함수를 엄청 간단하게 짜뒀다.. 본받자..