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

 

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

 

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

프로그래머스

---

 

해결전략

 

문자열, 

 

substr

 

isupper

tolower

---

 

코드

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

struct File{
    string head;
    int number;
    string tail;
	int index; // 입력 순서

    File(string a, int b, string c, int d)
    {
        head = a; number = b; tail = c; index = d;
    }

    // operator< 오버로딩: sort 함수에서 사용됨 
    // 먼저 head가 같다면 number로 비교하고 그 다음은 입력 순서(index)로 비교함
    bool operator<(const File& f)
	{
        if (head != f.head) {
            return head < f.head;
        }
        if (number != f.number) {
            return number < f.number;
        }
        return index < f.index; // 내가 실수한 부분. 아래 설명 참조
    }
};

vector<File> v;

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

    for(int i = 0; i < files.size(); i++)
    {
        string str = files[i];

        for (char& c : str) {
            if(isupper(c)) // 대문자라면
				c = tolower(c); // 소문자로 변환
        };

        string head = "", tail = "";
        int number=0;
        bool flag = false;
        int tmp = 0;

    	for(int j = 0; j < str.size(); j++)
        {
            if ('0' <= str[j] && str[j] <= '9' && flag == false) {
                tmp = j;
                flag = true;
	        }
            else if (!('0' <= str[j] && str[j] <= '9') && flag == true) {
                head = str.substr(0, tmp);
                number = stoi(str.substr(tmp, j-tmp)); // int형으로 변환하여 변수에 넣음
                tail = str.substr(j);
                break;
            }

            if (j == str.size() - 1) { // 마지막 문자열인 경우
                if (flag) { // 숫자가 이미 나온 경우
                    head = str.substr(0, tmp);
                    number = stoi(str.substr(tmp));
                    tail = "";
                }
            }
        }
        // 추후에 정렬하기 위해 v에 head, number, tail, i(=index)를 담음.
        v.push_back({ head, number, tail, i });
    }

    sort(v.begin(), v.end()); // 정렬. operator< 오버로딩 사용.

	for(int i = 0; i<v.size(); i++){
        answer.push_back(files[v[i].index]); // v 순서를 이용하여 answer에 담음
	}

    return answer;
}

int main()
{
    vector<string> testcase1 = { "img12.png", "img10.png", "img02.png", "img1.png", "IMG01.GIF", "img2.JPG" };
    vector<string> testcase2 = { "F-5 Freedom Fighter", "B-50 Superfortress", "A-10 Thunderbolt II", "F-14 Tomcat" };

    solution(testcase1);

    return 0;
}

 

 

※  return index < f.index; 해야 하는 이유

 

return index < f.index; 코드는 입력에서 주어진 원래의 순서를 유지하기 위한 목적으로 사용된다.

파일명을 정렬할 때, HEAD 부분과 NUMBER 부분이 동일한 파일들에 대해서는 원래의 입력 순서를 유지해야 한다. 이런 요구사항은 '안정 정렬(stable sort)'라고도 합니다.

C++의 std::sort 함수는 기본적으로 '불안정 정렬(unstable sort)'다. 즉, 동일한 값을 가진 요소들 사이의 상대적인 순서가 보장되지 않는다. 따라서 별도로 원래의 입력 순서를 추적하고 유지하는 방법이 필요하며, 이를 위해 각 파일마다 원래 인덱스(index)를 저장하고 사용한다.

따라서 return index < f.index; 코드는 두 파일의 HEAD와 NUMBER가 모두 같을 경우에만 실행되며, 이 경우 더 앞선 위치에 있던 파일이 더 앞쪽으로 오게 된다.

 

---

 

 

유사 풀이

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

struct File
{
    string head;
    int number;
	int index;

    File(string a, int b, int c){
        head = a; number = b; index = c;
    }

    bool operator<(const File& f) const
	{
        if(head != f.head){
            return head < f.head;
        }
        if(number != f.number){
            return number < f.number;
        }
        return index < f.index;
    }
};

vector<File> v;

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

	for(int i = 0; i<files.size(); i++)
    {
		string str = files[i];
		string head = "", num_str="";
		int j=0;

		while(j<str.size())
        {
			if(isdigit(str[j])) 
            	break;
            
			head += tolower(str[j]);
			j++;
		}

		while(j<str.size())
        {
			if(!isdigit(str[j])) 
            	break;
            
			num_str += str[j];
			j++;
		}

    	v.push_back({head , stoi(num_str), i});
   }

	sort(v.begin(), v.end()); // 정렬. operator< 사용

	for(int i=0;i<v.size();i++){
    	answer.push_back(files[v[i].index]);
   }

	return answer;
}

 

 

 

 

---