[2018_Blind_Kakao] 파일명 정렬

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

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

 

문자열 정렬 문제

 

C++의 경우 문자열 정렬 문제를 풀 때 STL의 sort를 사용한다면,

 

sort보다 stable_sort를 사용하는게 좋다

 

이유는 다음과 같다.

 

여기서 sort는 불안전한 정렬, stable_sort는 말 그대로 안정된 정렬이다.

 

sort는 퀵소트 기반, stable_sort는 머지소트 기반이다.

 

sort는 순서 보장이 안되지만 stable_sort는 순서 보장이 된다.

 

두 정렬의 차이를 이 문제의 테스트 케이스를 예시로 들면,

 

img01, img1의 경우 sort는 (img01, img1), (img1,img01) 이 두 경우중 하나를 반환한다.

 

즉, 01과 1을 같다고 생각하여 전자가 올 수 있고 혹은 후자가 올 수도 있다.

 

stable_sort는 순서를 보장하여 정렬한다.

 

문제 접근 방식은 숫자가 나오기 이전 까지 head, 숫자 영역은 number, 그 이후 영역은 tail로 놓고 풀었다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

bool stringCmp(pair<pair<pair<string, string>, string>, string> s1, pair<pair<pair<string, string>, string>, string> s2) {
	if (s1.first.first.first == s2.first.first.first) {
		return stoi(s1.first.first.second) < stoi(s2.first.first.second);
	}
	else
		return s1.first.first.first < s2.first.first.first;
}

vector<string> solution(vector<string> files) {
    vector<string> answer;
    vector<pair<pair<pair<string, string>, string>, string>> strLine;
	
	for (int i = 0; i < files.size(); i++) {
		string temp = files[i];

		string head, number, tail;
		int num = 0;

		for (int j = 0; j < temp.length(); j++) {
			if (temp[j] >= 48 && temp[j] <= 57) {
				num = j;
				break;
			}
			else {
				head += tolower(temp[j]);
			}
		}

		for (int j = num; j < temp.length(); j++) {
			if (temp[j] >= 48 && temp[j] <= 57) {
				number += temp[j];
			}
			else {
				num = j;
				break;
			}
		}

		tail = temp.substr(num);

		strLine.push_back({ { {head, number}, tail }, temp });
	}

	stable_sort(strLine.begin(), strLine.end(), stringCmp);

	for (int i = 0; i < strLine.size(); i++)
		answer.push_back(strLine[i].second);
    
    return answer;
}