프로그래머스 - [3차] 파일명 정렬 - C++

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

프로그래머스

 

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

bool compare(const pair<string,vector<string>>& a,const pair<string,vector<string>>& b)
{
    if(a.second[0]!=b.second[0])
        return a.second[0]<b.second[0];
    else
        return stoi(a.second[1])<stoi(b.second[1]);
}

vector<string> solution(vector<string> files) {
    vector<string> answer;
    vector<pair<string,vector<string>>> data;
    int idx=0;
    for(int i=0;i<files.size();i++)
    {
        vector<string> v(3);
        string t="";
        int j=0;
        for(j = 0;j<files[i].length();j++)
        {
            if(isdigit(files[i][j]))break;
            t+=tolower(files[i][j]);
        }
        v[0]=t;t="";
        int cnt=0;
        for(;cnt<5&&j<files[i].length();j++,cnt++)
        {
            if(!isdigit(files[i][j]))break;
            t+=files[i][j];
        }
        v[1]=t;
        v[2]= "";
        data.push_back({files[i],v});
    }
    
    stable_sort(data.begin(),data.end(),compare);
    for(int i=0;i<data.size();i++)
        answer.push_back(data[i].first);
    return answer;
}

주어진 조건에 따라 파일명을 정렬하는 문제이다. 

우선 문자열을 파싱해야한다. 

 

vector<string> v(3);
        string t="";
        int j=0;
        for(j = 0;j<files[i].length();j++)
        {
            if(isdigit(files[i][j]))break;
            t+=tolower(files[i][j]);
        }
        v[0]=t;t="";
        int cnt=0;
        for(;cnt<5&&j<files[i].length();j++,cnt++)
        {
            if(!isdigit(files[i][j]))break;
            t+=files[i][j];
        }
        v[1]=t;

for문 안에서 숫자가 나올 때까지의 문자열을 head로 두번째에서는 숫자가 아닌 문자가 나올때까지의 문자열을 number로 지정하여 v에 저장한다. 

이를 바탕으로 정렬을 실행한다.

 

bool compare(const pair<string,vector<string>>& a,const pair<string,vector<string>>& b)
{
    if(a.second[0]!=b.second[0])
        return a.second[0]<b.second[0];
    else
        return stoi(a.second[1])<stoi(b.second[1]);
}

head가 같지않으면 오름차순으로, 같다면 number를 정수로 바꿔서 오름차순으로 정렬을 시킨다. 

 

여기서 중요한 점이 있다. 

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

이 정렬함수이다. 

기존 sort 함수를 사용했는데 실패가 떠서 1시간가량을 해맸다. 

sort는 퀵 또는 힙정렬로 구현돼있어서 초기순서를 보장하지않는 불안정형 정렬함수이다. 

그래서 실패가 떴던 것이다. 

stable_sort는 병합정렬로 구현돼있어서 초기순서를 보장하는 안정형 정렬이다. 

따라서 이 문제에서는 stable_sort함수를 써서 구현해야한다.