[프로그래머스] [3차] 파일명 정렬 C++ 풀이 및 해설

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

프로그래머스

 

풀이 방법

head, number, tail 부분으로 분할하여 string 3개(head, number, tail)를 저장하여

compare 함수(정렬 함수)를 만들어 정렬한다.

이때 head가 같은경우 number를 비교하도록 compare 함수를 작성한다.

정렬된 string 3개를 붙여 순서대로 answer 벡터에 넣으면 된다.

 

C++로 풀때 sort 함수를 사용하면 동일한 값에 대해 정렬은 불안정 정렬하게 된다.

즉, 같은 값에 대해 상대적인 위치를 보장해주지 않는다.

stable_sort 함수를 통해 정렬을하면 정답처리가 된다...

 

(처음에 sort 함수가 문제인지 찾은 사람은 천재인걸까...

대단하다. sort 함수를 사용하고 계속 틀리길래 분할에서 문제가 있었는지 좀 헤맸다...)

전체 코드

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

bool compare(pair<string,pair<string,string>> v1, pair<string,pair<string,string>> v2) {
    
    /* 일시적으로 소문자로 바꿈 */
    for(int i=0; i<v1.first.length(); i++) {
        v1.first[i] = tolower(v1.first[i]);
    }
    for(int i=0; i<v2.first.length(); i++) {
        v2.first[i] = tolower(v2.first[i]);
    }
    
    /* head가 동일하다면 */
    if(v1.first==v2.first) {
        int i1 = stoi(v1.second.first);
        int i2 = stoi(v2.second.first);
        if(i1<i2)
            return true;
        else
            return false;
    } else { /* head가 동일하지 않다면 */
        if(v1.first<v2.first)
            return true;
        else
            return false;
    }
    
}

vector<string> solution(vector<string> files) {
    vector<string> answer;
    vector<pair<string,pair<string,string>>> v; // <head<number,tail>>
    for(int i=0; i<files.size(); i++) {
        string head="";
        string number="";
        string tail="";
        bool headFlag=true;
        bool numberFlag=false;
        bool tailFlag=false;
        for(int idx=0; idx<files[i].length(); idx++) {
            if(headFlag) {
                head += files[i][idx];
                
                /* 다음 문자가 숫자라면 */
                if(idx+1<files[i].length() && files[i][idx+1]>='0' && files[i][idx+1]<='9') {
                    headFlag=false; numberFlag=true;
                }
            } else if(numberFlag) {
                number += files[i][idx];
                
                /* 다음 문자가 숫자가 아니라면 */
                if(idx+1<files[i].length() && (files[i][idx+1]<'0' || files[i][idx+1]>'9')) {
                    numberFlag=false; tailFlag=true;
                } else if(idx+1<files[i].length() && number.length()==5) { // number가 5개인 상태라면
                    tail += files[i][idx+1]; // 현재 문자를 tail에 추가하고
                    numberFlag=false; tailFlag=true; // Flag 변경
                }
            } else {
                tail += files[i][idx];
            }
        }
        v.push_back(make_pair(head,make_pair(number,tail)));
    }
    
    stable_sort(v.begin(), v.end(), compare); // compare 함수를 통해 정렬
    
    /* 정렬된 v 벡터를 하나하나 붙여 answer에 추가 */
    for(int i=0; i<v.size(); i++) {
        answer.push_back(v[i].first+v[i].second.first+v[i].second.second);
    }
    return answer;
}