알고리즘 문제 - 파일명 정렬

프로그래머스 문제

https://school.programmers.co.kr/learn/courses/30/lessons/17686?language=cpp

#include <string>
#include <vector>
// add
#include <algorithm>

using namespace std;

struct filename
{
    std::string head;
    int num;
    int idx;
};

bool compare(filename& f1, filename& f2)
{
    if (f1.head == f2.head) {
        if (f1.num == f2.num)
            return f1.idx < f2.idx;
        return f1.num < f2.num;
    }
    return f1.head < f2.head;
}

vector<string> solution(vector<string> files) {
    vector<string> answer;
    vector<filename> list;
    for (int i = 0; i < files.size(); ++i)
    {
        size_t pos1 = files[i].find_first_of("0123456789", 0);
        size_t pos2 = files[i].find_first_not_of("0123456789", pos1);
        if (pos2 == files[i].npos)
            pos2 = files[i].size() - 1;
        std::string head = files[i].substr(0, pos1);
        std::transform(head.begin()
                      , head.end()
                      , head.begin()
                      , [](unsigned char c) { return std::tolower(c); });
        
        list.push_back({head, stoi(files[i].substr(pos1, pos2)), i});
    }
    std::sort(list.begin(), list.end(), compare);
    for (auto& e : list)
        answer.push_back(files[e.idx]);
    
    return answer;
}

/* lambda function instead */
#include <string>
#include <vector>
// add
#include <algorithm>

using namespace std;

struct filename
{
    std::string head;
    int num;
    int idx;
};

vector<string> solution(vector<string> files) {
    vector<string> answer;
    vector<filename> list;
    for (int i = 0; i < files.size(); ++i)
    {
        size_t pos1 = files[i].find_first_of("0123456789", 0);
        size_t pos2 = files[i].find_first_not_of("0123456789", pos1);
        if (pos2 == files[i].npos)
            pos2 = files[i].size() - 1;
        std::string head = files[i].substr(0, pos1);
        std::transform(head.begin()
                      , head.end()
                      , head.begin()
                      , [](unsigned char c) { return std::tolower(c); });
        
        list.push_back({head, stoi(files[i].substr(pos1, pos2)), i});
    }
    std::sort(list.begin(), list.end(), [](filename &f1, filename &f2) {
        if (f1.head == f2.head) {
            if (f1.num == f2.num)
                return f1.idx < f2.idx;
            return f1.num < f2.num;
        }
        return f1.head < f2.head;
    });
    for (auto& e : list)
        answer.push_back(files[e.idx]);
    
    return answer;
}

Memo

• std::string 멤버 함수 find_first_of(), find_first_not_of()
• std::transform()
• std::sort()

std::sort - cppreference.com

std::transform - cppreference.com

std::basic_string<CharT,Traits,Allocator>::find_first_of - cppreference.com

std::find, std::find_if, std::find_if_not - cppreference.com