[C++로 풀이] 파일명 정렬 (정렬, stable sort) ⭐⭐

Date: 2021.02.09 Updated: 2021.02.09

카테고리: Programmers

📌 파일명 정렬

난이도 ⭐⭐

🚀 문제

🚀 내 풀이 ⭕

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

using namespace std;

bool cmp(const string& a, const string& b) {
    
    /* HEAD */
    string a_HEAD = "";
    int a_index = 0;
    while (a_index < a.length()) {
        if (a[a_index] >= '0' && a[a_index] <= '9')
            break;
        else {
            a_HEAD += tolower(a[a_index]);
            a_index++;
        }
    }
    string b_HEAD = "";
    int b_index = 0;
    while (b_index < b.length()) {
        if (b[b_index] >= '0' && b[b_index] <= '9')
            break;
        else {
            b_HEAD += tolower(b[b_index]);
            b_index++;
        }
    }

    if (a_HEAD != b_HEAD)
        return a_HEAD < b_HEAD;

    /* NUMBER */
    string a_NUMBER = "";
    for (int i = 0; i < 5 && a_index < a.length(); i++) {
        if (a[a_index] >= '0' && a[a_index] <= '9') {
            a_NUMBER += a[a_index];
            a_index++;
        }
        else break;
    }
    string b_NUMBER = "";
    for (int i = 0; i < 5 && b_index < b.length(); i++) {
        if (b[b_index] >= '0' && b[b_index] <= '9') {
            b_NUMBER += b[b_index];
            b_index++;
        }
        else break;
    }
    int a_num = stoi(a_NUMBER);
    int b_num = stoi(b_NUMBER);
    if (a_num != b_num)
        return a_num < b_num;
}

vector<string> solution(vector<string> files) {
    vector<string> answer = files;
    stable_sort(answer.begin(), answer.end(), cmp);
    return answer;
}

stable_sort 👉 원래의 입력 순서를 유지하면서 정렬시킨다. (sort 처럼 algorithm 헤더에 있다.)

sort 👉 비교하는 두 값이 같으면 랜덤하게 순서를 정한다.
stable_sort 👉 비교하는 두 값이 같으면 입력 순서대로 정렬한다.

우선 순위 3 순위의 정렬 기준은 입력 순서를 그대로 유지해야 하기 때문에 이 정렬은 stable_sort 함수를 사용해 정렬하는 것이 좋겠다.

정렬 기준
1. HEAD의 사전 순 정렬 (대소문자 구분 X)
2. HEAD가 같다면 👉 NUMBER의 숫자 순 정렬 (5글자까지가 최대)
3. HEAD도, NUMBER도 같다면 👉 입력 순 정렬
  - ✨stable_sort 함수를 사용해야 하는 이유! (일반 sort 함수를 쓴다면 HEAD와 NUMBER가 같은 것 끼리는 랜덤한 순서로 정렬될 것이다.)

✈ 비교 함수 만들기

bool cmp(const string& a, const string& b)

여담으로 비교함수의 기본 데이터 타입인 매개변수는 꼭 const를 붙여주어야 한다. pair, vector 같은 컨테이너 제외.

정렬 기준 1 순위 : HEAD 의 사전 순서

    /* HEAD */
    string a_HEAD = "";
    int a_index = 0;
    while (a_index < a.length()) {
        if (a[a_index] >= '0' && a[a_index] <= '9')
            break;
        else {
            a_HEAD += tolower(a[a_index]);
            a_index++;
        }
    }
    string b_HEAD = "";
    int b_index = 0;
    while (b_index < b.length()) {
        if (b[b_index] >= '0' && b[b_index] <= '9')
            break;
        else {
            b_HEAD += tolower(b[b_index]);
            b_index++;
        }
    }

    if (a_HEAD != b_HEAD)
        return a_HEAD < b_HEAD;

HEAD 부분은 문자로만 이루어진다. 그리고 대소문자를 구분하지 않는다.

두 HEAD가 같지 않다면 이 문자열 HEAD의 사전 순대로 오름차순 정렬하고 비교함수를 빠져나오면 된다.
여기까지 완료하면 a_index, b_index에는 각각 두 비교 대상 문자열의 숫자가 시작되는 NUMBER 부분의 시작 인덱스가 담기게 된다.

정렬 기준 2 순위 : NUMBER 의 숫자 크기

    /* NUMBER */
    string a_NUMBER = "";
    for (int i = 0; i < 5 && a_index < a.length(); i++) {
        if (a[a_index] >= '0' && a[a_index] <= '9') {
            a_NUMBER += a[a_index];
            a_index++;
        }
        else break;
    }
    string b_NUMBER = "";
    for (int i = 0; i < 5 && b_index < b.length(); i++) {
        if (b[b_index] >= '0' && b[b_index] <= '9') {
            b_NUMBER += b[b_index];
            b_index++;
        }
        else break;
    }
    int a_num = stoi(a_NUMBER);
    int b_num = stoi(b_NUMBER);
    if (a_num != b_num)
        return a_num < b_num;

NUMBER 부분은 숫자로만 이루어진다. 최대 5글자까지 나올 수 있으며, 0012은 곧 12 와 같다. (정수 변환이 필요하단 얘기)

위 정렬 기준 1 순위에서 리턴되지 않았다면 두 HEAD가 같다는 얘기다. 이럴 경우에는 이제 NUMBER끼리 비교를 해야 한다.
NUMBER 문자열을 결정할 때 반복 조건
1. 최대 5 개만 저장할 수 있음
2. TAIL은 없을 수도 있기 때문에 NUMBER이 5글자도 안되어 문자열이 끊길 수 있으므로 런타임 에러를 대비해 인덱스가 문자열 길이보다 작은지도 검사해주어야 함.
3. 숫자 일 때만 반복
두 숫자가 같지 않다면 숫자 크기 순대로 오름차순 정렬하고 비교함수를 빠져나오면 된다.

정렬 기준 3 순위 : 입력 순서

1순위, 2순위에서 리턴되지 않았다면 HEAD도 NUMBER도 같다는 것이다. stable_sort 로 정렬했기 때문에 이 경우엔 자동으로 입력 순서로 정렬이 된다.

vector<string> solution(vector<string> files) {
    vector<string> answer = files;
    stable_sort(answer.begin(), answer.end(), cmp);
    return answer;
}

이렇게 완성한 비교함수로 stable_sort 시켜주면 된다.

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️