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

문제

 

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

프로그래머스

문제풀이

 

함수 2개와 stable_sort의 compare 함수를 구현했다.

함수는 대소문자 구분을 하지 않으므로 모든 대문자를 소문자로 변환하는 lower함수,

입력받은 문자열에는 띄어쓰기가 없으므로 istringstream 대신 직접 파싱 하는 findNum 함수이다.

 

소문자 변환 함수는 string의 문자 하나하나 tolower을 통해 바꾼다.

 

pii findNum(string str) {
    int start(0), end(0), prev(-1);
    for (int idx = 0; idx < str.size(); ++idx) {
        if (isdigit(str[idx]) != 0) {
            if (start == 0) start = idx;
            end = idx;
        }
        else if (isdigit(str[idx]) == 0 && end != 0) break;
    }
    return { start, end };
}

문자열로 "img12.png"가 들어오는 경우 숫자 12에 해당하는 인덱스를 찾기 위한 함수이다.

isdigit을 통해 해당 문자가 숫자인지 판별을 한다.

숫자인 경우 start가 0이면 start를 한 번만 갱신한다. 

숫자인 경우 end는 계속 현재 idx값으로 갱신한다.

만약 해당 문자가 숫자가 아니고 end가 이미 갱신됐다면 break를 통해 반복문을 종료한다.

 

bool cmp(string s1, string s2) {
    string head1(""), head2("");
    int number1(0), number2(0);
    int start(0), end(0);

    pii ret = findNum(s1);
    start = ret.first, end = ret.second;

    head1 = lower(s1.substr(0, start));
    number1 = stoi(s1.substr(start, end - start + 1));

    ret = findNum(s2);
    start = ret.first, end = ret.second;

    head2 = lower(s2.substr(0, start));
    number2 = stoi(s2.substr(start, end - start + 1));

    if (head1 == head2) {
        return number1 < number2;
    }
    return head1 < head2;
}

문제에서 중요한 건 head와 number이다. tail은 구하지 않아도 된다.

 

미리 구현한 findNum함수를 통해 s1의 숫자의 시작지점, 끝지점을 구한다.

그다음 head와 number을 start, end, substr을 통해 파싱 한다.

s2도 같은 방법으로 구한다.

 

문제의 조건대로 head가 같으면 number가 작은 순, head가 같지 않다면 head가 작은 순으로 return 한다.

만약 head가 같고 number가 같은 경우는 stable_sort에 의해 입력된 순으로 그대로 정렬된다. (바뀌지 않는다)

 

코드

#include <string>
#include <vector>
#include <cctype>
#include <algorithm>
#define pii pair<int, int>
using namespace std;

string lower(string str) {
    string ret("");
    for (int idx = 0; idx < str.size(); ++idx) {
        ret += tolower(str[idx]);
    }
    return ret;
}

pii findNum(string str) {
    int start(0), end(0), prev(-1);
    for (int idx = 0; idx < str.size(); ++idx) {
        if (isdigit(str[idx]) != 0) {
            if (start == 0) start = idx;
            end = idx;
        }
        else if (isdigit(str[idx]) == 0 && end != 0) break;
    }
    return { start, end };
}

bool cmp(string s1, string s2) {
    string head1(""), head2("");
    int number1(0), number2(0);
    int start(0), end(0);

    pii ret = findNum(s1);
    start = ret.first, end = ret.second;

    head1 = lower(s1.substr(0, start));
    number1 = stoi(s1.substr(start, end - start + 1));

    ret = findNum(s2);
    start = ret.first, end = ret.second;

    head2 = lower(s2.substr(0, start));
    number2 = stoi(s2.substr(start, end - start + 1));

    if (head1 == head2) {
        return number1 < number2;
    }
    return head1 < head2;
}

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