[프로그래머스]2018 KAKAO BLIND RECRUITMENT : 파일명 정렬 (level 2)(c++)

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

코딩테스트 연습 - [3차] 파일명 정렬

 

방법 1: struct에 헤드, 숫자, 입력 순서값 저장해서 정렬

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

using namespace std;

// 헤드, 숫자, 입력순서를 저장할 구조체
struct file_info {
    string head;
    int number;
    int index;
};

// 헤드, 숫자, 입력 순서 순으로 비교
bool compare(file_info first, file_info second)
{
    int order = first.head.compare(second.head);
    if (order != 0)
    {
        return order < 0;
    }
    if (first.number != second.number)
    {
        return first.number < second.number;
    }
    return first.index < second.index;
}

vector<string> solution(vector<string> files) {

    vector<file_info> infos;
    for (int i = 0; i < files.size(); ++i)
    {
        string file = files[i];

        // 헤드 만들기 (모두 대문자로)
        string head;
        int end = 0;
        while (!isdigit(file[end]))
        {
            file[end] = toupper(file[end]);
            ++end;
        }

        // 숫자 만들기
        int num = 0;
        while (isdigit(file[end]))
        {
            num *= 10;
            num += file[end] - '0';
            ++end;
        }

        // infos벡터에 헤드, 숫자, 입력순서 구조체 저장
        file_info f = { head, num, i };
        infos.push_back(f);
    }

    // 헤드, 숫자, 입력 순서 순으로 정렬
    sort(infos.begin(), infos.end(), compare);

    // answer벡터에 infos에서 정렬된 인덱스에 해당하는 file명 저장
    vector<string> answer;
    for (auto iter = infos.begin(); iter != infos.end(); ++iter)
    {
        answer.push_back(files[iter->index]);
    }

    return answer;
}

 

방법 2: stable_sort 사용 (이 문제에선 비추)

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

using namespace std;

// 문자에서 등장하는 첫번째 숫자의 인덱스 구하기
int get_first_num_idx(string s)
{
    int idx = 0;
    while (!isdigit(s[idx]))
    {
        ++idx;
    }
    return idx;
}

// 문자 순서 비교 (오름차순) 
bool head_cmp(string first, string second)
{
    int first_num = get_first_num_idx(first);
    int second_num = get_first_num_idx(second);

    string f_string = first.substr(0, first_num);
    string s_string = second.substr(0, second_num);

    transform(f_string.begin(), f_string.end(), f_string.begin(), ::toupper);
    transform(s_string.begin(), s_string.end(), s_string.begin(), ::toupper);

    int order = f_string.compare(s_string);
    return order < 0;
}

// 문자에서 주어진 인덱스부터 시작하는 숫자값 구하기
int make_num(int idx, string s)
{
    int num = 0;
    while (idx < s.size() && isdigit(s[idx]))
    {
        num *= 10;
        num += s[idx] - '0';
        ++idx;
    }
    return num;
}

// 숫자 순서 비교 (오름차순)
bool num_cmp(string first, string second)
{
    int f_idx = get_first_num_idx(first);
    int s_idx = get_first_num_idx(second);

    return make_num(f_idx, first) < make_num(s_idx, second);
}

vector<string> solution(vector<string> files) {
    
    /*
        입력 순서를 유지해야 하므로 stable_sort로 안정 정렬
        head 순 정렬이 더 우선이기 때문에, 
        숫자 정렬을 먼저 하고 head정렬을 나중에 한다.
    */
    stable_sort(files.begin(), files.end(), num_cmp);
    stable_sort(files.begin(), files.end(), head_cmp);

    return files;
}

 

방법2는 stable_sort 한번 써보려고 연습한거지,

방법1로 구조체 이용해서 푸는게 훨씬 낫다.

 

일단 속도가 빠르고, 메모리 차이가 없다.

방법 2는 따로 저장하는게 없어서 메모리를 덜먹을 것 같지만,

두 문자를 비교하는 compare fucntor에서 쓸데없이 여러번 문자와 숫자를 만들게 된다.

 

반면 구조체에 정보를 저장하면 딱 한번씩만 만들고

그다음은 비교만 하면 되니 훨씬 빠르다.