[프로그래머스] 17686번 - 파일명 정렬 (구현, 2018 KAKAO BLIND RECRUITMENT)

1. 문제 및 예제

 

 간단하게 문자열을 다루는 문제였다. 문자열을 입력에 맞게 나누는 것은 어렵지 않았지만, 안정 정렬에 관한 지식이 있었어야 했다. C++같은 경우는 관련 정렬 함수를 지원해주었지만 미리 알지 않았으면 큰일날뻔 했다...

---

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

프로그래머스

---

2. 풀이과정

 

 안정 정렬을 알고있으면, compare함수를 커스텀하여 풀 수 있는 문제이다. 문제를 다음처럼 쪼개보았다.

 

1. 문자열을 전부 소문자로 변경한다.

2. HEAD, NUMBER, TAIL로 나눠 Vector에 담는다.

3. comp함수를 제작하여 알고리즘별로 정렬.

 

 다음은 입력된 문자열을 소문자로 변경하는 함수이다.

 

string get_lower(string str){
    string tmp = "";
    for(auto it : str){
        if('A' <= it && it <= 'Z'){
            tmp += (it + ('a' - 'A'));
        }else{
            tmp += it;
        }
    }
    return tmp;
}

 

다음은 문자열을 나누는 함수이다.

 

vector<string> get_nums(string str){
    int index = 0;
    int start = 0;
    vector<string> result;
    
    for(int i = 0; i < str.size(); i++){
        if( '0' <= str[i] && str[i]<= '9'){
            index = i;
            break;
        }
    }
    
    result.push_back(get_lower(str.substr(0, index)));
    start = index;
    
    for(index = start; index < 5 + start; index++){
        if( !('0' <= str[index] && str[index]<= '9')){
            break;
        }
    }
    result.push_back(str.substr(start, index - start));
    result.push_back(str.substr(index, str.size() - index));
    
    return result;
}

 

 다음은 정렬 커스텀 함수이다.

 

bool compare(string str1, string str2){
    vector<string> str1_list = get_nums(str1);
    vector<string> str2_list = get_nums(str2);
    
    if(str1_list[0] == str2_list[0]){
        if(stoi(str1_list[1]) == stoi(str2_list[1])){
            return false;
        }else{
            return stoi(str1_list[1]) < stoi(str2_list[1]);
        }
    }else
        return str1_list[0] < str2_list[0];
}

 

 다음은 전체 코드이다.

 

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

using namespace std;

string get_lower(string str){
    string tmp = "";
    for(auto it : str){
        if('A' <= it && it <= 'Z'){
            tmp += (it + ('a' - 'A'));
        }else{
            tmp += it;
        }
    }
    return tmp;
}

vector<string> get_nums(string str){
    int index = 0;
    int start = 0;
    vector<string> result;
    
    for(int i = 0; i < str.size(); i++){
        if( '0' <= str[i] && str[i]<= '9'){
            index = i;
            break;
        }
    }
    
    result.push_back(get_lower(str.substr(0, index)));
    start = index;
    
    for(index = start; index < 5 + start; index++){
        if( !('0' <= str[index] && str[index]<= '9')){
            break;
        }
    }
    result.push_back(str.substr(start, index - start));
    result.push_back(str.substr(index, str.size() - index));
    
    return result;
}

bool compare(string str1, string str2){
    vector<string> str1_list = get_nums(str1);
    vector<string> str2_list = get_nums(str2);
    
    if(str1_list[0] == str2_list[0]){
        if(stoi(str1_list[1]) == stoi(str2_list[1])){
            return false;
        }else{
            return stoi(str1_list[1]) < stoi(str2_list[1]);
        }
    }else
        return str1_list[0] < str2_list[0];
}

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

 

3. 결어

 

안정 정렬과 관련된 구현문제였다. 안정 정렬에 대해서는 공부가 더 필요할 것 같다.