[알고리즘 / C++] Stable Sort

프로그래머스 [3차] 파일명 정렬 문제 풀다가 알게된 개념

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

struct File{
    string head, num, tail;
    int number;
};

vector<File> file;

int StrToInt(string s)
{
    int num = 0;
    
    for(char c : s)
    {
        num = (num * 10) + (c - '0');
    }
    return (num);
}

void sepFile(string s)
{
    File f;
    int i=0;
    string fName = "";
    
    for(; i<s.size(); i++)
    {
        if('0' <= s[i] && s[i] <= '9')
            break;
        fName += s[i];
    }
    f.head = fName;
    fName = "";
    for(; i<s.size(); i++)
    {
        if(!('0' <= s[i] && s[i] <= '9'))
            break;
        fName += s[i];
    }
    f.num = fName;
    f.number = StrToInt(fName);
    fName = "";
    for(; i<s.size(); i++) fName += s[i];
    f.tail = fName;
    file.push_back(f);
}

File mkLower(File f)
{
    for(int i=0; i<f.head.size(); i++)
    {
        if('A' <= f.head[i] && f.head[i] <= 'Z')
        {
            f.head[i] = f.head[i] - 'A' + 'a';
        }
    }
    return (f);
}

bool Cmp(const File &a, const File &b)
{
    File aa = mkLower(a);
    File bb = mkLower(b);
    
    if(aa.head < bb.head)
        return (true);
    else if(aa.head == bb.head)
    {
        if(aa.number < bb.number)
            return (true);
        else
            return (false);
    }
    else
        return (false);
}

string FileToStr(File f)
{
    string s = "";
    
    s += f.head;
    s += f.num;
    s += f.tail;
    return (s);
}

vector<string> solution(vector<string> files) {
    vector<string> answer;
    
    for(string f : files)
    {
        sepFile(f);
    }
    stable_sort(file.begin(), file.end(), Cmp);
    for(File f : file)
    {
        string s = FileToStr(f);
        answer.push_back(s);
    }
    return answer;
}

위의 코드에서 'stable_sort' 대신 'sort'를 사용하면 테스트케이스의 일부가 실패로 나온다.

sort 함수는 불안정 정렬(unstable sort)를 구현하기 때문이다.

["img01.png", "img1.JPG"]와 같은 예시가 있을 때, 문제에 의하면 해당 순서는 바뀌어선 안 된다.

하지만 sort 함수에서는 이 기존 순서를 보장해주지 않는다. 정렬 과정에서 둘의 순서가 바뀔 수 있다.

따라서 순서를 보장해주는 stable_sort를 사용해야 통과가 된다.

 

참고

• https://school.programmers.co.kr/questions/17636
• https://velog.io/@cookncoding/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90-Stable-Sort-Inplace