[C++] sort vs stable_sort

🎯 문제

정렬 기준

입출력

🥏 접근 방식

문제 접근은 어렵지 않았습니다.

우선 파일명을 {head, number, tail}로 구성된 벡터로
반환하는 split 함수를 작성하고
이를 기준으로 정렬하는 로직을 구성했습니다.

split은 파일명을 순차적으로 탐색하면서
숫자가 등장하기 이전의 string을 head로,
이후 최대 5글자까지 숫자가 등장하는 string을 number로,
나머지 부분을 tail로 나누었습니다.

정렬 시 head를 소문자로 변환하는 것도 잊지 않았으나
마주한 건 의외의 실패 러쉬..
(10%즘 맞았던 걸로 기억합니다..)

분명 테스트 케이스에선 문제없이 잘 돌아갔는데 말이죠.
로직에서도, 구현 기능에서도 오류를 찾지 못해
실패한 이유를 이리저리 찾아봤습니다.

🗿 std::sort의 문제점

문제는 내장 함수 std::sort에 있었습니다.
C++에서 std::sort는 비교하는 값이 같은 경우
기존 순서를 보장하지 않습니다.
이 때문에 위 제약조건을 만족하지 못해서 그 많은 실패가..

기존 순서를 보전하고 싶은 경우는
std::sort 대신 std::stable_sort 사용을 권장하더군요.

이러한 차이는 두 내장 함수의
서로 다른 내부 정렬 로직으로 인해 발생합니다.
std::sort의 경우 내부적으로 Quick Sort로 구현된 것에 반해,
std::stable_sort는 Merge Sort로 구현되었습니다.

전자의 경우는 정렬 중 인덱스가 변경될 수 있지만,
후자의 경우 분할 과정에서 기존 인덱스의 순서를 보전하기에
상대적으로 안정적입니다.

일반적으로 속도는 std::sort 쪽이 빠르다고 하지만
이전에 정리해 둔 주요 정렬 로직들의 시간 복잡도를 살펴보면
두 로직 모두 $O(NlogN)$을 따르기에 큰 차이는 없을 듯 싶습니다.

오히려 Quick Sort는 최악의 경우 $O(N^2)$을 따르기에
std::sort가 더 느린 경우도 있지 않을까 싶지만
여건 상 따로 테스트는 해보지 않았습니다.

✍️ 후기

간편한 라이브러리에 너무 익숙해지다보니
기존 정렬 함수들에 대한 이해가 흐리멍텅해졌다는 걸
확인할 수 있던 문제였습니다.

배우는 입장에서 정렬만큼은 라이브러리를 벗어나
직접 구현하는게 바람직하다고
머리로는 생각하지만 몸이 따라주지 않았기에
이런 사단이 난 게 아닐까란 반성도 드네요..

구현 자체는 어렵지 않은 문제였기에
시간은 30분 내외로 풀어냈습니다.

최근 프로그래머스 Level 2정도의
문자열, 구현 문제를 자주 접해서 그런지
C++로 문자열을 파싱하는게
다른 언어들보다 오히려 편하게 느껴집니다.

많은 분들이 문자열 문제는 파이썬으로 해결하시던데
저도 2학년 땐 그랬던 듯 싶고.. 괜히 그립네요.

요즘 CV 쪽도 가볍게 학습해보고 싶은 마음이 들어
'다시 파이썬을 익혀볼까'하는 생각도 듭니다.

그래도 C++을 사용해 문자열을 처리하는 훈련을 하면
인덱스를 다룸에 있어서 정확도와 이해도가
타 언어보다 섬세해지는 부분도 있어
얻는 이점도 많다고 생각합니다. (C++ 최고!)

✅ 구현

#include <bits/stdc++.h>

using namespace std;

string convert(string str)
{
    string ret = "";
    for(auto c: str)
    {
        if(c >= 'A' && c <= 'Z')
        {
            c += 'a' - 'A';
        }
        ret += c;
    }
  
    return ret;
}

vector<string> split(string str)
{
    string head = "";
    string numStr = "";
    string tail = "";
  
    int headIdx, numIdx, tailIdx;
    for(headIdx = 0; headIdx<str.size(); headIdx++)
    {
        char now = str[headIdx];
        if(now < '0' || now > '9')
        {
            head += now;
        }
        else break;
    } 
 
    for(numIdx = headIdx; numIdx<str.size(); numIdx++)
    {
        char now = str[numIdx];
        if(now >= '0' && now <= '9' && numStr.size() < 5)
        {
            numStr += now;
        }
        else break;
    }
   
    tailIdx = numIdx;
  
    if(tailIdx < str.size())
        tail = str.substr(tailIdx);
 
    return {convert(head), numStr, tail};
}

vector<string> solution(vector<string> files) {
  
    stable_sort(files.begin(), files.end(),
        [](const string& left, const string& right){
            vector<string> l = split(left);
            vector<string> r = split(right);
          
            if(l[0] != r[0])
                return l[0] < r[0];
            else
                return stoi(l[1]) < stoi(r[1]);
        });
  
    return files;
}

📚 참고자료

관련 블로그 - sort vs stable_sort