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

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

코딩테스트 연습 - [3차] 파일명 정렬 | 프로그래머스

 본 문제는 '2018 KAKAO BLIND RECRUITMENT'로 kakao Tech에 의하면 "정답률 66.95%, 언어별로는 C++과 Python 사용자들이 힘들어함."라고 한다. c++에서 주로 sort는 unstable_sort인 quick sort로 이 문제에서 제시된 "두 파일의 HEAD 부분과, NUMBER의 숫자도 같을 경우, 원래 입력에 주어진 순서를 유지한다." 조건 때문에 TC 1, 2를 제외한 나머지 TC에서 틀리게 된다.

 간단히 stable_sort와 unstable_sort에 대해 설명하자면, stable_sort는 중복된 값의 순서 유지를 보장, unstable_sort는 순서 유지를 보장하지 않는다. 

• stable_sort - bubble, insertion, merge
• unstable sort - selection, quick, heap 로 분류된다.

 따라서, 문제를 풀기위해서는 stable_sort를 사용해야 하는데 C++에서는 stable_sort를 지원한다.

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
typedef struct divi { //파일명 구분
    string head;
    string num;
    string tail;
} divi;
 
bool cmp(divi a, divi b) {
    string x;
    string y;
    // head의 값을 비교하기 위해 대문자로 변경
    for (int i = 0; i < a.head.size(); i++) {
        x += toupper(a.head[i]);
    }
    for (int i = 0; i < b.head.size(); i++) {
        y += toupper(b.head[i]);
    }
    if (x.compare(y) == 0) { // head가 같을 때,
        return stoi(a.num) < stoi(b.num); // num을 비교한다.
    }
    if (x.compare(y) < 0) return true;
    else return false;
}
 
vector<string> solution(vector<string> files) {
    vector<string> answer;
    vector<divi> v;
    for (int i = 0; i < files.size(); i++) {
        int index = 0;
        divi tmp;
        tmp.head = "";
        tmp.num = "";
        tmp.tail = "";
        // head는 숫자가 아닌 문자로 이루어져 있기 때문에, 숫자가 나오면 break.
        while (index != files[i].size()){
            if ((files[i][index] < '0' || files[i][index] > '9')) tmp.head += files[i][index];
            else break;
            index += 1;
        }
        // num
        while (index != files[i].size()) {
            if (files[i][index] >= '0' && files[i][index] <= '9') tmp.num += files[i][index];
            else break;
            index += 1;
        }
        // tail
        while (index != files[i].size()) {
            tmp.tail += files[i][index];
            index += 1;
        }
        v.push_back(tmp);
    }
    stable_sort(v.begin(), v.end(), cmp);
    
    for (int i = 0; i < v.size(); i++) {
        string tmp = "";
        tmp += v[i].head;
        tmp += v[i].num;
        tmp += v[i].tail;
        answer.push_back(tmp);
    }
    return answer;
}

<채점 결과>