[알고리즘] 프로그래머스_파일명 정렬

본 블로그는 비상업적, 비영리적 용도의 학업만을 위해 글을 게시합니다.

1. 문제 분석

• 파일명을 나눠서 HEAD(string) - NUMBER(int) 순으로 오름차순 정렬하는 문제이다.
• TAIL은 상관 없고, HEAD, NUMBER 둘 다 같으면 입력 순서대로라서 stable한 sort가 필요하다.

2. 문제 풀이 과정(삽질)

• tuple을 써봤는데, 익숙하지 않아서 조금 걸렸다.

3. 문제 해결

• 분석대로 진행했다.

4. 코드

#include <string>
#include <vector>
#include <tuple>
#include <algorithm>
#include <iostream>

using namespace std;

bool compare(tuple<string, string, int> fileA, tuple<string, string, int> fileB)
{
    int numA, numB;
    string headA, headB;
    
    tie(ignore, headA, numA) = fileA;
    tie(ignore, headB, numB) = fileB;
    
    if(headA == headB)
    {
        if(numA == numB)
            return false;
        return numA < numB;
    }
    return headA < headB;
}

string lowerCase(string s)
{
    for(int i = 0; i < s.length(); i++)
        if(s[i] >= 'A' && s[i] <= 'Z')
            s[i] += 32;
    return s;
}

int findNum(string filename, int pos)
{
    for(int i = pos; i <= filename.length(); i++)
        if(filename[i] >= '0' && filename[i] <= '9')
            return i;
    return -1;
}

int findTail(string filename, int pos)
{
    for(int i = pos; i <= filename.length(); i++)
        if(filename[i] > '9' || filename[i] < '0')
            return i;
    return -1;
}

vector<string> solution(vector<string> files) {
    int pos1 = 0, pos2 = 0;
    string filename = "";
    vector<string> answer;
    tuple<string, string, int> fileT;
    vector<tuple<string, string, int>> filesT;
    
    for(int i = 0; i < files.size(); i++)
    {
        filename = files[i];
        get<0>(fileT) = filename;
        filename = lowerCase(filename);
        pos1 = findNum(filename, 0);
        pos2 = findTail(filename, pos1 + 1);
        
        get<1>(fileT) = filename.substr(0, pos1);
        get<2>(fileT) = stoi(filename.substr(pos1, pos2 - pos1));
        
        filesT.push_back(fileT);
    }
    stable_sort(filesT.begin(), filesT.end(), compare);
    for(auto i : filesT)
        answer.push_back(get<0>(i));
    return answer;
}

5. 고수의 코드를 보고 배우기

• 함수 네이밍을 makeLower나 findNumIdx같은 것들이 차이가 난다.
• transform이라는 라이브러리 함수를 써서 변환 함수를 한번에 적용하는 것도 새로 알았다.
• 정렬 방법에서 새로운 방법을 배웠다.
  • 보통은 pair나 tuple로 두 변수에 대해 compare 함수를 처리했다.
  • NUMBER(후순위)를 먼저 stable 정렬해주고, HEAD(선순위)도 stable 정렬해주니, 원하는 정렬이 되었다. 뭐가 더 효율적일지는 모르겠다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cctype>
using namespace std;
char makeLower(char c)
{
    if (c >= 'A' && c <= 'Z') c += 'a' - 'A';
    return c;
}
int findNumIdx(const string &str)
{
    int i;
    for (i = 0; i < str.length(); i++)
    {
        if (str[i] >= '0' && str[i] <= '9')
            break;
    }
    return i;
}
int getNumber(string str)
{
    return std::stoi(str.substr( findNumIdx(str) ));
}
string getHeader(string str)
{
    string rtn = str.substr(0, findNumIdx(str));

    std::transform(rtn.begin(), rtn.end(), rtn.begin(), makeLower);

    return rtn;
}

bool numComp(string str1, string str2) { return getNumber(str1) < getNumber(str2); }
bool headComp(string str1, string str2) { return getHeader(str1).compare(getHeader(str2)) < 0; }

vector<string> solution(vector<string> files)
{   
    std::stable_sort(files.begin(), files.end(), numComp);

    std::stable_sort(files.begin(), files.end(), headComp);

    return files;
}