파일명 정렬
파일명은 크게 HEAD, NUMBER, TAIL의 세 부분으로 구성된다.
HEAD는 숫자가 아닌 문자로 이루어져 있으며, 최소한 한 글자 이상이다.
NUMBER는 한 글자에서 최대 다섯 글자 사이의 연속된 숫자로 이루어져 있으며, 앞쪽에 0이 올 수 있다. 0부터 99999 사이의 숫자로, 00000이나 0101 등도 가능하다.
TAIL은 그 나머지 부분으로, 여기에는 숫자가 다시 나타날 수도 있으며, 아무 글자도 없을 수 있다.
파일명 HEAD NUMBER TAIL foo9.txt foo 9 .txt foo010bar020.zip foo 010 bar020.zip F-15 F- 15 (빈 문자열) 파일명을 세 부분으로 나눈 후, 다음 기준에 따라 파일명을 정렬한다.
파일명은 우선 HEAD 부분을 기준으로 사전 순으로 정렬한다. 이때, 문자열 비교 시 대소문자 구분을 하지 않는다. MUZI와 muzi, MuZi는 정렬 시에 같은 순서로 취급된다.
파일명의 HEAD 부분이 대소문자 차이 외에는 같을 경우, NUMBER의 숫자 순으로 정렬한다. 9 < 10 < 0011 < 012 < 13 < 014 순으로 정렬된다. 숫자 앞의 0은 무시되며, 012와 12는 정렬 시에 같은 같은 값으로 처리된다.
두 파일의 HEAD 부분과, NUMBER의 숫자도 같을 경우, 원래 입력에 주어진 순서를 유지한다. MUZI01.zip과 muzi1.png가 입력으로 들어오면, 정렬 후에도 입력 시 주어진 두 파일의 순서가 바뀌어서는 안 된다.
무지를 도와 파일명 정렬 프로그램을 구현하라.
문제 해결 과정
HEAD, NUMBER, TAIL을 구분하여vector<vector<string>> v에 push하고, 정렬하기 위해 STL sort()를 사용하였고, 비교함수를 다음과 같이 작성했다.
bool compare(vector<string> &v1, vector<string> &v2){
if(toLower(v1[0]) == toLower(v2[0])){
return stoi(v1[1]) < stoi(v2[1]);
}
return toLower(v1[0]) < toLower(v2[0]);
}sort()가 안정 정렬을 제공하는 줄 알고 사용했는데, 제출하니 예제 두개 빼곤 모두 틀렸다고 나온다.
알고보니 sort()는 불안정 정렬이었고, 안정 정렬은 stable_sort()를 사용해야 했다.
stable_sort()를 따로 제공한다는 것을 이번에 처음 앎...😭
수정 후 돌렸는데.. 이번엔 에러가 떴다.
error: binding reference of type 'vector<...>' to value of type 'vector<...>' drops 'const' qualifier
검색해보니 non-constant인 객체를 constant인 객체에 바인드하는 것에서 에러가 생긴 것이었다.
따라서 compare 함수 인자에 const를 붙여주었더니 간단히 에러가 해결되었다.
bool compare(const vector<string> &v1, const vector<string> &v2){
if(toLower(v1[0]) == toLower(v2[0])){
return stoi(v1[1]) < stoi(v2[1]);
}
return toLower(v1[0]) < toLower(v2[0]);
}근데 sort()함수 일때는 에러가 없다가, stable_sort()일 때만 에러가 발생한다.. 왜일까?
전체 코드
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
string toLower(string a){
for(int i=0; i<a.length(); i++){
if(a[i] >= 'A' && a[i] <= 'Z'){
a[i] = a[i] - 'A' + 'a';
}
}
return a;
}
bool compare(const vector<string> &v1, const vector<string> &v2){
if(toLower(v1[0]) == toLower(v2[0])){
return stoi(v1[1]) < stoi(v2[1]);
}
return toLower(v1[0]) < toLower(v2[0]);
}
vector<string> solution(vector<string> files) {
vector<string> answer;
vector<vector<string>> v;
for(int i=0; i<files.size(); i++){
bool flag = 0;
int ns = 0, ts = files[i].length();
for(int j=0; j<files[i].length(); j++){
if(!flag && files[i][j] >='0' && files[i][j] <= '9'){
flag = 1;
ns = j;
}
else if(flag && (files[i][j] <'0' || files[i][j] > '9' || j - ns >= 5)){
ts = j;
break;
}
}
string head = files[i].substr(0, ns);
string number = files[i].substr(ns, ts-ns);
string tail = files[i].substr(ts);
vector<string> file;
file.push_back(head);
file.push_back(number);
file.push_back(tail);
v.push_back(file);
}
stable_sort(v.begin(), v.end(), compare);
for(int i=0; i<v.size(); i++){
string result = v[i][0] + v[i][1] + v[i][2];
answer.push_back(result);
}
return answer;
}