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

문제 바로가기

접근방법

신입사원 무지가 파일 관리 담당업무를 맡게 되었다.
무지는 파일 이름 (예시) hello8384.jpg 을 hello를 header, 8384를 number, .jpg를 tail
이렇게 3등분 하였고 header > number > tail 순으로 정렬을 하려고 한다. (사실 tail 단계에서 정렬을 하는건 없고 number까지 같다면 입력받은 순서 그대로 출력면된다.

1. 현재 있는 파일들을 header, number, tail로 다 구분한 값들을 vector에 저장하자
2. sort함수를 이용해 정렬하자 (compare함수를 내가 만들어야함)
3. 결과물 출력

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

using namespace std;

struct fileName{ string head,num,tail;}; 

string mkupper(string a){ //대문자로 만들어주는 함수
    for(int i = 0 ; i< a.length(); i++) a[i] = toupper(a[i]);
    return a;
}
bool cmp(fileName a, fileName b){
    string a1 = mkupper(a.head), b1 = mkupper(b.head);
    if(a1 < b1) return true;
    else if(a1 == b1){
        if(stoi(a.num) < stoi(b.num)) return true;
        else if(stoi(a.num) >= stoi(b.num)) return false;
    }else return false;
}

vector<string> solution(vector<string> files) {
    vector<string> answer;
    vector<fileName> arr;    
    for(int i = 0 ; i <files.size(); i++){
        fileName a;
        string x="",y="",z="";
        bool fst = true,scnd = false,thrd= false;
        int k = files[i].length();
        for(int j = 0 ; j<k; j++){
            if(fst){
                x += files[i][j];
                if(j + 1 == k || isdigit(files[i][j+1])){
                    fst = false;
                    scnd = true;
                    a.head = x;
                    continue;
                }
            }else if(scnd){
                y += files[i][j];
                    if(j + 1 == k || !isdigit(files[i][j+1])){
                        scnd = false;
                        thrd = true;
                        a.num = y;
                        continue;
                    }
            }else if(thrd) z += files[i][j];
        }
        a.tail = z;
        arr.push_back(a);
    }

    stable_sort(arr.begin(),arr.end(),cmp);//중요
    
    for(int i = 0 ; i < arr.size(); i++){
        string str = "";
        str = str + arr[i].head + arr[i].num + arr[i].tail;
        answer.push_back(str);
    }
    return answer;
}

이 문제를 풀으면서 stable_sort를 처음 알게 되었다.
stable sort란 말 그대로 안정 정렬이라는 뜻인데, 이게 무슨 뜻이냐면 정렬시에 중복값들의 원래 순서가 바뀌지 않는다는 것이다. (그렇다면 불안정 정렬도 있겠지?)

예를 들어보자
5 3 2 1 2 이렇게 수가 있을 때
안정정렬은 [ 5, 3, 2(1), 1, 2(2) ] --> [ 1, 2(1), 2(2), 3, 5 ]이렇게 즉 중복값들의 원래 순서를 보장해준다.
불완정 정렬은 [ 5, 3, 2(1), 1, 2(2) ] -->[ 1, 2(1or2), 2(2or1), 3, 5 ] 이렇게 중복 값들의 원래 순서를 보장 못해주는것이다.
대표적인 불완정 정렬이 우리가 자주 사용하는 sort함수다.