[Algorithm] Programmers :: 파일명 정렬

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

프로그래머스

struct Node
{
    string origin;
    string head;
    int number;
};
 
bool cmp(const Node& a, const Node& b)
{
    if (a.head == b.head)
    {
        return a.number < b.number;
    }
 
    return a.head < b.head;
}
 
vector<string> solution(vector<string> files)
{
    vector<string> answer;
    vector<Node> nodes;
 
    for (int i = 0; i < files.size(); ++i)
    {
        string origin = files[i];
        string head;
        string number;
        bool isCheck = false;
 
        for (int j = 0; j < files[i].size(); ++j)
        {
            files[i][j] = tolower(files[i][j]);
            
            if (files[i][j] >= '0' && files[i][j] <= '9')
            {
                number += files[i][j];
                isCheck = true;
            }
            else if (!isCheck)
            {
                head += files[i][j];
            }
            else break;
        }
 
        nodes.push_back({ origin, head, stoi(number) });
    }
 
    stable_sort(nodes.begin(), nodes.end(), cmp);
 
    for (int i = 0; i < nodes.size(); ++i)
    {
        answer.push_back(nodes[i].origin);
    }
 
    return answer;
}

 

기본적으로 head와 number만 잘 분류하면 크게 어렵지 않은 문제이다.

단 여기서 중요한 조건이 있다. 

조건에 의해 우선순위가 같다면, 즉 head랑 number를 따져도 우선순위가 같다면 '순서가 변경되어선 안된다' 라는 조건이다.

 

이게 왜 중요하냐면, 자주 사용하는 그냥 sort의 경우 불완전한 정렬이다. 

우선순위가 같으면 순서가 변경되면 안되는데 변경이 되어버리는 경우가 발생한다.

예를들어 img01과 img1은 우선순위가 완벽히 똑같다. 그렇다면 정답을 출력할때 반드시 img01, img1 순서 그대로 출력해야된다.

하지만 기존에 쓰던 sort를 사용할 경우 img1 img01 처럼 순서가 바껴서 나오는 경우가 있다.

 

해결법은 간단하다. sort대신 stable_sort를 사용하면 된다...