프로그래머스 - [3차] 파일명 정렬 [C++]

 이 문제는 주어진 대로 구현하여 푸는 문제이다. 이 문제에서 중요한 건 HEAD와 NUMBER이고, TAIL은 정렬 기준에 아예 없으므로 구하지 않아도 된다. 일단 가장 중요한 조건은 HEAD와 NUMBER까지 같을 때, 처음 순서 그대로 유지되어야 한다는 것이다. 처음에는 이를 무시하고 일단 넣고 정렬하면 알아서 그대로 될 것이라 생각했지만, 오답이 나왔다. 나는 구조체를 이용해서 index들을 저장했지만, 다른 방식을 사용하더라도 반드시 그대로 넣는 로직이 들어가야 한다. 이 문제에서는 STL sort를 사용할 때 compare 함수를 선언하여 정렬 기준을 설정할 수 있다는 사실과, string을 그대로 비교할 수 있다는 사실만 알고 있으면 어렵지 않게 풀 수 있다.

 

 

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

using namespace std;

struct node {
    string head;
    int number;
    vector<int> index;
};

bool compare(node& a, node& b) {
    if (a.head == b.head) {
        return a.number < b.number;
    }
    return a.head < b.head;
}

vector<string> solution(vector<string> files) {
    vector<string> answer;
    
    vector<node> tempFiles;
    
    for (int i = 0; i < files.size(); i++) {
        string present = files[i];
        int index = 0;
        node temp;
        
        // find head
        string head = "";
        while (!('0' <= present[index] && present[index] <= '9')) {
            char c = present[index];
            if ('A' <= c && c <= 'Z') {
                c += 'a' - 'A';
            }
            head += c;
            index++;
        }
        
        // find number
        string num = "";
        while (('0' <= present[index] && present[index] <= '9') && index < files[i].size()) {
            num += present[index];
            index++;
        }
        int number = stoi(num);
        
        // find same
        bool flag = true;
        for (node& nod : tempFiles) {
            if (nod.head == head && nod.number == number) {
                flag = false;
                (nod.index).push_back(i);
                break;
            }
        }
        if (flag) {
            temp.head = head;
            temp.number = number;
            (temp.index).push_back(i);
            tempFiles.push_back(temp);
        }
    }
    
    sort(tempFiles.begin(), tempFiles.end(), compare);
    
    for (node& t : tempFiles) {
        for (int idx : t.index) {
            answer.push_back(files[idx]);
        }
    }
    
    return answer;
}