[3차] 파일명 정렬(2018 카카오 블라인드 채용)

문제 링크

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

 

 

풀이

조건이 많은 것은 주석을 다는 습관을 다지고 있다.

주석에 대해서 요약해보자면

 

* 요약

// 선행 처리

1) answer에 복사생성자를 통해 files를 미리 복사

2) files를 모두 대문자로 변환(cctype과 algorithm 헤더가 필요)

 

// 처리

1) 파일명 분할(vector<pair<string, vector<string>>>을 선언하여 first는 본래의 string, second는 part별로 나눈 string을 저장하였다. (answer가 first에 들어간다, 이유는 대문자로 변환된 files가 들어가선 안되기 때문)

 

// 후처리

1) cmp 함수를 정의하여 정렬할 때 세 번째 조건에서 인덱싱을 바꿔선 안되기 때문에 '='이 들어가지 않게 첫 번째 조건과 두 번째 조건을 정의하였다.

2) stable_sort 함수 이용, 병합정렬(중요!!), 일반 sort(): 퀵정렬을 이용하면 안된다.(why. 같다는 조건이 두 번 들어갈 수 있으므로 불안정한 퀵정렬은 사용 X), 저도 처음에 틀린...

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cctype>       // for ::toupper

using namespace std;

// HEAD: 문자만(최소 1글자), NUMBER: 0~99999(string) 0000, 0101도 가능
// TAIL: 숫자 가능, 비어있을 수도 ---> HEAD + NUMBER + 나머지 부분(= TAIL)

bool cmp(pair<string, vector<string>> p1, pair<string, vector<string>> p2){
    if(p1.second[0] == p2.second[0]) 
        return stoi(p1.second[1]) < stoi(p2.second[1]);
    return p1.second[0] < p2.second[0];
}

vector<string> solution(vector<string> files) {
    vector<string> answer(files);
    
    // part별로 나누어진 files
    vector<pair<string, vector<string>>> partFiles;
    
    // 선행 처리(대소문자 구분X)
    for(string& s: files){      // 참조자로
        transform(s.begin(), s.end(), s.begin(), ::toupper);
    }
    
    // 파일명 분할(HEAD + NUMBER + 나머지)
    for(int i=0; i<files.size(); i++){
        vector<string> temp;
        string s = files[i];
        int pos=0;
        while(pos < s.length()){
            if(s[pos] >= '0' && s[pos] <= '9') break;
            pos++;
        }
        temp.push_back(s.substr(0, pos));           // Input HEAD
        int from = pos;
        while(pos<s.length()){
            if(s[pos] < '0' || s[pos] > '9') break;
            pos++;
        }
        temp.push_back(s.substr(from, pos-from));   // Input NUMBER
        if(pos != s.length())
            temp.push_back(s.substr(pos));          // Input TAIL
        partFiles.push_back(make_pair(answer[i], temp));
    }   
    
   
    
    // 파일명 정렬
    // 1. HEAD 부터(사전 순, 대소문자 구분X, = 안들어가게)
    // 2. NUMBER의 숫자 크기 순(HEAD가 같을 때)
    // 3. 입력된 순서대로
    stable_sort(partFiles.begin(), partFiles.end(), cmp);
    
    for(int i=0; i<partFiles.size(); i++){
        answer[i] = partFiles[i].first;
        // cout<<answer[i]<<endl;
    }
    
    return answer;
}