[알고리즘] 프로그래머스_파일명 정렬
본 블로그는 비상업적, 비영리적 용도의 학업만을 위해 글을 게시합니다.
1. 문제 분석
- 파일명을 나눠서 HEAD(string) - NUMBER(int) 순으로 오름차순 정렬하는 문제이다.
- TAIL은 상관 없고, HEAD, NUMBER 둘 다 같으면 입력 순서대로라서 stable한 sort가 필요하다.
2. 문제 풀이 과정(삽질)
- tuple을 써봤는데, 익숙하지 않아서 조금 걸렸다.
3. 문제 해결
- 분석대로 진행했다.
4. 코드
#include <string>
#include <vector>
#include <tuple>
#include <algorithm>
#include <iostream>
using namespace std;
bool compare(tuple<string, string, int> fileA, tuple<string, string, int> fileB)
{
int numA, numB;
string headA, headB;
tie(ignore, headA, numA) = fileA;
tie(ignore, headB, numB) = fileB;
if(headA == headB)
{
if(numA == numB)
return false;
return numA < numB;
}
return headA < headB;
}
string lowerCase(string s)
{
for(int i = 0; i < s.length(); i++)
if(s[i] >= 'A' && s[i] <= 'Z')
s[i] += 32;
return s;
}
int findNum(string filename, int pos)
{
for(int i = pos; i <= filename.length(); i++)
if(filename[i] >= '0' && filename[i] <= '9')
return i;
return -1;
}
int findTail(string filename, int pos)
{
for(int i = pos; i <= filename.length(); i++)
if(filename[i] > '9' || filename[i] < '0')
return i;
return -1;
}
vector<string> solution(vector<string> files) {
int pos1 = 0, pos2 = 0;
string filename = "";
vector<string> answer;
tuple<string, string, int> fileT;
vector<tuple<string, string, int>> filesT;
for(int i = 0; i < files.size(); i++)
{
filename = files[i];
get<0>(fileT) = filename;
filename = lowerCase(filename);
pos1 = findNum(filename, 0);
pos2 = findTail(filename, pos1 + 1);
get<1>(fileT) = filename.substr(0, pos1);
get<2>(fileT) = stoi(filename.substr(pos1, pos2 - pos1));
filesT.push_back(fileT);
}
stable_sort(filesT.begin(), filesT.end(), compare);
for(auto i : filesT)
answer.push_back(get<0>(i));
return answer;
}
5. 고수의 코드를 보고 배우기
- 함수 네이밍을 makeLower나 findNumIdx같은 것들이 차이가 난다.
- transform이라는 라이브러리 함수를 써서 변환 함수를 한번에 적용하는 것도 새로 알았다.
- 정렬 방법에서 새로운 방법을 배웠다.
- 보통은 pair나 tuple로 두 변수에 대해 compare 함수를 처리했다.
- NUMBER(후순위)를 먼저 stable 정렬해주고, HEAD(선순위)도 stable 정렬해주니, 원하는 정렬이 되었다. 뭐가 더 효율적일지는 모르겠다.
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cctype>
using namespace std;
char makeLower(char c)
{
if (c >= 'A' && c <= 'Z') c += 'a' - 'A';
return c;
}
int findNumIdx(const string &str)
{
int i;
for (i = 0; i < str.length(); i++)
{
if (str[i] >= '0' && str[i] <= '9')
break;
}
return i;
}
int getNumber(string str)
{
return std::stoi(str.substr( findNumIdx(str) ));
}
string getHeader(string str)
{
string rtn = str.substr(0, findNumIdx(str));
std::transform(rtn.begin(), rtn.end(), rtn.begin(), makeLower);
return rtn;
}
bool numComp(string str1, string str2) { return getNumber(str1) < getNumber(str2); }
bool headComp(string str1, string str2) { return getHeader(str1).compare(getHeader(str2)) < 0; }
vector<string> solution(vector<string> files)
{
std::stable_sort(files.begin(), files.end(), numComp);
std::stable_sort(files.begin(), files.end(), headComp);
return files;
}
Author And Source
이 문제에 관하여([알고리즘] 프로그래머스_파일명 정렬), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@fortice/알고리즘-프로그래머스파일명-정렬저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)