프로그래머스 - 2018 KAKAO BLIND RECRUITMENT[3차] 파일명 정렬

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

프로그래머스

 

주어진 문자열을 조건에 맞게 HEAD, NUMBER, TAIL을 분리하고 그에 따른 정렬을 사용하면 된다.

 

그런데 중요한 것은 

 

HEAD 와 NUMBER가 같을 경우엔 TAIL이 달라도 순서를 그대로 진행시켜야한다. 같은 우선순위를 가진 경우를 컨트롤하는 것이 문제의 관건이다. 

 

C++ Algorithm의 sort는 불안정 정렬이다. 만약 A B C D 에서 sort했을 때 A와 B의 우선순위가 같다면 변하지 않아야 맞는 연산이지만 일반적인 sort에서는 B A C D 가 나올 수 있다는 뜻이다.

 

https://en.cppreference.com/w/cpp/algorithm/stable_sort

std::stable_sort - cppreference.com

 

출처 : c++ 레퍼런스

 

 

 

그때 유용한 정렬이 stable_sort이다. 이 정렬은 기존의 순서가 중요할 경우 사용하게 된다. 다만, 최악의 경우에도 N log N 의 시간복잡도를 유지하는 불안정 sort와 달리 N (log N)^2 까지 늘어날 수 있다.

 

이 문제의 경우 이 방법 외에 index를 추가하는 방법이 있다.

 

/*
    comp 함수를 만들어서, HEAD, NUMBER, TAIL을 분리 후 각 순서로 정렬

    comp와 분류 distribute 함수도 추가
*/

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

struct file{
    string HEAD = "";
    int NUM = 0;
    string TAIL = "";
};

file makeFile(string str){
    string stk = "";
    
    file f;
    
    bool h = false;
    bool n = false;
    for(int i = 0; i < str.size(); i++){
        if(h == false){
            if(str[i] <= '9' && str[i] >= '0'){
                h = true;
                f.HEAD = stk;
                stk = toupper(str[i]);
                
                continue;
            }            

        }else if(n == false) {
            if(str[i] > '9' || str[i] < '0') {
                n = true;
                f.NUM = stoi(stk);
                stk = toupper(str[i]);
                
                continue;
            }
        }
        stk += toupper(str[i]);
    } 
    
    if(n == false){
        f.NUM = stoi(stk);
    }else{
        f.TAIL = stk;
    }
    
    return f;
}


bool comp(string A, string B){
    file Afile = makeFile(A);
    file Bfile = makeFile(B);
    
    if(Afile.HEAD == Bfile.HEAD) {
        return Afile.NUM < Bfile.NUM;
    }else{
        return Afile.HEAD < Bfile.HEAD;
    }
}

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