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

파일명 정렬

문제 링크

[3차] 파일명 정렬

분석

파일명을 HEAD, NUMBER를 기준으로 정렬하는 문제입니다.

HEAD는 파일명에서 숫자가 나오기 전까지의 문자열입니다.
대소문자를 구분하지 않고 사전순으로 정렬합니다.

NUMBER은 HEAD 다음에 오는 숫자 부분으로 최대 5자리까지 제한이 있습니다.
해당 부분의 숫자 앞에 0은 불필요합니다.

만약, HEAD와 NUMBER가 같으면 원래 입력 순서를 유지해야합니다.
이를 위해 stable_sort함수를 사용해 정렬하는 것이 좋습니다.

임의의 기준으로 정렬이 필요하므로, 사용자 정의 정렬 함수를 구현해야합니다.
HEAD와 NUMBER에 구분이 있으므로, 이를 분리할 수 있는 로직이 필요합니다.

풀이

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

using namespace std;

// 문자열의 HEAD 부분을 소문자로 변환하여 반환하는 함수
string lowerHead(string str)
{
    string lowerHead;
    for (int i = 0; i < str.size(); ++i)
    {
        // 숫자가 나오면 HEAD 끝
        if (isdigit(str[i]))
        {
            break;
        }
        
        // 소문자로 변환하여 저장
        lowerHead += tolower(str[i]);
    }
    
    return lowerHead;
}

// 문자열에서 NUMBER 부분을 추출하여 정수로 반환하는 함수
int getNumber(string str)
{
    // 문자열에서 첫 번째 숫자의 위치 찾기
    auto firstDigitIt = find_if(str.begin(), str.end(), [](char c)
                                { return isdigit(c); });
    int firstDigitIndex = distance(str.begin(), firstDigitIt);
    
    // 숫자가 끝나는 위치 찾기
    auto endDigitIt = firstDigitIt;
    while (endDigitIt != str.end() && isdigit(*endDigitIt))
    {
        ++endDigitIt;
    }
    
    // 숫자의 길이 계산
    int length = distance(firstDigitIt, endDigitIt);
    
    // 숫자 부분 문자열 추출
    string numStr = str.substr(firstDigitIndex, length);
    
    // 문자열을 정수로 변환하여 반환
    return stoi(numStr);
}

// 바일 이름을 비교하는 기준 함수
bool compare(string a, string b)
{
    string aHead = lowerHead(a);
    string bHead = lowerHead(b);
    
    // HEAD 사전순 비교
    if (aHead != bHead)
    {
        return aHead < bHead;
    }
    
    int aNum = getNumber(a);
    int bNum = getNumber(b);
    
    // NUMBER 순서 비교
    if (aNum != bNum)
    {
        return aNum < bNum;
    }
    
    // HEAD와 NUMBER가 같으면 입력 순서를 유지
    return false;
}

vector<string> solution(vector<string> files) {
    // 입력 순서를 유지하기 위해 안정 정렬을 사용한다.
    stable_sort(files.begin(), files.end(), compare);

    return files;
}

성능 요약

시간 복잡도는 $O(K log K \times N)$입니다.

• lowerHead 함수 $O(N)$
• getNumber 함수 $O(N)$
  • find_if, while문의 연산이 최대 $O(N)$
  • substr, stoi의 연산이 $O(M)$
• compare 함수에서 lowerHead, getNumber를 호출 $O(N)$
• stable_sort 함수 $O(K log K)$
• $O(N) + O(K log K)$

공간 복잡도는 $O(K + N)$입니다.

• lowerHead 함수에서 새로운 문자열 생성 $O(N)$
• getNumber 함수에서 부분 문자열 생성 $O(N)$
• stable_sort 함수는 병합 정렬 기반으로 $O(K)$
• $O(N) + O(N) + O(K)$

테스트 성능

정확성 테스트

테스트 1 〉통과 (0.02ms, 3.79MB)
테스트 2 〉통과 (0.02ms, 3.75MB)
테스트 3 〉통과 (2.12ms, 4.05MB)
테스트 4 〉통과 (2.43ms, 3.97MB)
테스트 5 〉통과 (2.34ms, 4.08MB)
테스트 6 〉통과 (2.16ms, 4.05MB)
테스트 7 〉통과 (2.03ms, 4.19MB)
테스트 8 〉통과 (1.82ms, 4.12MB)
테스트 9 〉통과 (1.95ms, 4.01MB)
테스트 10 〉통과 (1.89ms, 4.02MB)
테스트 11 〉통과 (1.89ms, 4MB)
테스트 12 〉통과 (2.29ms, 4.19MB)
테스트 13 〉통과 (1.35ms, 4.19MB)
테스트 14 〉통과 (2.37ms, 4.18MB)
테스트 15 〉통과 (2.48ms, 4.2MB)
테스트 16 〉통과 (1.97ms, 4.19MB)
테스트 17 〉통과 (1.23ms, 4.07MB)
테스트 18 〉통과 (1.24ms, 4.2MB)
테스트 19 〉통과 (1.36ms, 4.13MB)
테스트 20 〉통과 (1.39ms, 4.2MB)