알고리즘(C++) / 프로그래머스 level 2 : 파일명 정렬

level 2 : 파일명 정렬

https://programmers.co.kr/learn/courses/30/lessons/17686?language=cpp 

코딩테스트 연습 - [3차] 파일명 정렬

 

코드

//프로그래머스 파일명 정렬
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

bool cmp(vector<string> a, vector<string> b) {
    if (a[0] != b[0]) {
        return a[0] < b[0];
    }
    else {
        return stoi(a[1]) < stoi(b[1]);
    }
}


vector<string> solution(vector<string> files) {
    vector<string> answer;

    vector<vector<string>> file_hnt; // head, number, tail, original 순

    for (int i = 0; i < files.size(); i++) {
        vector<string> file;
        string head = "";
        string number = "";
        string tail = "";
        bool check = false;
        int j = 0;
        while (1) {
            if (isdigit(files[i][j])) {
                break;
            }
            else {
                if (islower(files[i][j])) { //소문자일때
                    head += (files[i][j] - 32); //대문자로 변환
                }
                else {
                    head += files[i][j];
                }
                j++;
            }
            //head
        }
        while (1) {
            if (isdigit(files[i][j])) {
                number += files[i][j]; //number
                j++;
            }
            else {
                break;
            }
        }

        for (int k = j; k < files[i].size(); k++) {
            if (islower(files[i][j])) { //소문자일때
                tail += (files[i][j] - 32); //대문자로 변환
            }
            else {
                tail += files[i][j];
            }
        }

        file.push_back(head); // head
        file.push_back(number); //number
        file.push_back(tail); //tail
        file.push_back(files[i]); //origin

        file_hnt.push_back(file);
    }

    stable_sort(file_hnt.begin(), file_hnt.end(), cmp); //안정 정렬

    for (int i = 0; i < file_hnt.size(); i++){
        answer.push_back(file_hnt[i][3]);
    }

    return answer;
}

int main() {
    vector<string> files = { "img12.png", "img10.png", "img02.png", "img1.png", "IMG01.GIF", "img2.JPG" };
    
    solution(files);

    return 0;
}

 

설명

파일명에서 HEAD와 NUMBER, TAIL을 구분하여 vector를 저장하였고 대소문자는 구분되지 않으므로 소문자일 때를 판단하여 대문자로 변환하였다. 그 후 원래 파일명을 벡터에 마지막으로 넣어주었다. 

안정 정렬(stable_sort)로 파일을 정렬하였다. 안정 정렬은 중복된 값을 입력 순서와 동일하게 정렬하는 알고리즘이므로 HEAD와 NUMBER의 숫자가 같을 경우 원래 입력에 주어진 순서를 유지할 수 있다. 

cmp 함수는 다음과 같이 같지 않을 때 'return a[0] < b[0];'로 정렬할 수 있다. 

 

고찰

이번 문제는 생각할 것들이 많았던 문제였다.

안정 정렬뿐만 아니라 cmp 함수, 대소문자 판단하는 것도 까다로웠다.

중복된 값을 입력 순서와 동일하게 정렬하기 위해 '안정 정렬(stable_sort)' 알고리즘을 사용해야 한다. 

대소문자 구분하지 않기 위해서 대문자를 소문자로 모두 바꾸거나 소문자를 대문자로 모두 바꿔 문제를 해결해야 한다. 이미 문자를 바꿨기 때문에 원래의 파일명을 알 수 있도록 벡터에 함께 저장할 수 있었다.