[프로그래머스/알고리즘] 파일명 정렬

파일명 정렬

문제풀다가 몰라서 해설을 보았습니다. sort에서 stable_sort로 바꾸자마자 통과되네요 ㅠㅠ

입출력 예제

입력 값 : ["img12.png", "img10.png", "img02.png", "img1.png", "IMG01.GIF", "img2.JPG"]

출력 값 : ["img1.png", "IMG01.GIF", "img02.png", "img2.JPG", "img10.png", "img12.png"]

해결 방법

2차원 배열로 이용해서 head와 number를 구해줍니다. 저는 그냥 while문 돌려가지고 숫자가 나오기 전까지 head 그다음 문자가 나오기 전까지 number로 하고 남은 것은 tail에 붙여줬습니다. 나중에 이어붙여야 하기 때문이죠

그리고 2차원 배열을 정렬 함수를 이용해서 해결해줍니다.

head를 전부 대문자로 바꾸고 compare함수를 이용해서 문자가 같으면 숫자가 작은 순으로 정렬하고 그 외에는 사전순으로 정렬해줍니다.

여기서 문제는 정렬함수를 sort를 쓰면 안된다는 겁니다(이것때문에 해설..)

C++기준으로 sort는 퀵정렬입니다. 퀵정렬은 같은 데이터를 비교할때 서로 바꿔주기 때문입니다. 문제는 같은 문자와 숫자일 경우에는 그대로 나둬야 하기 때문에 퀵정렬로 사용하면 에러가 납니다.(불안정한 정렬이라고 하네요, 책에서 봤지만 이게 진짜 중요한지 몰랐네요)

그렇기 때문에 다른 정렬인 병합정렬(stable_sort), 힙정렬(sort_heap)를 쓰셔야 안정한 정렬로 문제가 통과되네요.

소스 코드

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

using namespace std;
bool Pred(vector<string> a, vector<string> b) {
	string a1;
	string b1;
	for (int i = 0; i<a[0].size(); i++) {
		a1 += toupper(a[0][i]);
	}
	for (int i = 0; i<b[0].size(); i++) {
		b1 += toupper(b[0][i]);
	}
	if (a1.compare(b1) == 0) {
		return stoi(a[1])<stoi(b[1]);
	}
	if (a1.compare(b1)>0)
		return false;
	else
		return true;
}

vector<string> solution(vector<string> files) {
	vector<string> answer;
	vector<vector<string>> data(files.size(),vector<string>(3));

	int temp = 0;
	int j=0;
	for (int i = 0; i < files.size(); i++) {
		j = 0;
		temp = 0;
		while (j < files[i].size()){
			if ((files[i][j] < '0'||files[i][j] > '9')) {
				data[i][temp] += files[i][j];
			}
			else {
				temp++;
				break;
			}
			j++;
		}
		while (j < files[i].size()) {
			if (files[i][j] >= '0'&&files[i][j] <= '9') {
				data[i][temp] += files[i][j];
			}
			else {
				temp++;
				break;
			}
			j++;
		}
		while (j < files[i].size()) {
			data[i][temp] += files[i][j];
			j++;
		}
	}
	stable_sort(data.begin(), data.end(), Pred);
	
	for (int i = 0; i < files.size(); i++) {
		answer.push_back(data[i][0]+data[i][1] + data[i][2]);
	}
	return answer;
}