[프로그래머스 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;
}
'⭐ 코딩테스트 > 프로그래머스' 카테고리의 다른 글
[프로그래머스 C++] [1차] 프렌즈4블록 (0) | 2023.10.27 |
---|---|
[프로그래머스 C++] 롤 케이크 자르기 (0) | 2023.10.25 |
[프로그래머스 C++] 오픈채팅방 (0) | 2023.10.23 |
[프로그래머스 C++] 전력망을 둘로 나누기 (0) | 2023.10.19 |
[프로그래머스 C++] 더 맵게 (0) | 2023.10.18 |
댓글
이 글 공유하기
다른 글
-
[프로그래머스 C++] [1차] 프렌즈4블록
[프로그래머스 C++] [1차] 프렌즈4블록
2023.10.27 -
[프로그래머스 C++] 롤 케이크 자르기
[프로그래머스 C++] 롤 케이크 자르기
2023.10.25 -
[프로그래머스 C++] 오픈채팅방
[프로그래머스 C++] 오픈채팅방
2023.10.23 -
[프로그래머스 C++] 전력망을 둘로 나누기
[프로그래머스 C++] 전력망을 둘로 나누기
2023.10.19