[2018 KAKAO BLIND RECRUITMENT[3차]] 파일명

programmers.co.kr/learn/courses/30/lessons/17686

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

알고리즘 포스팅은 안 하는데, 척 봤을 때 못 풀 것 같은 문제였는데

40분 만에 디버깅 없이 풀어서 올려봅니다. 그래도 시간은 꽤 오래 걸린 것 같아요

코드 다시 살펴보면 오래 걸리거나 생각할 부분이 특별히 없는데, 왤케 오래걸렸는지는 모르겠습니다ㅜ

approve 받고나서 바로 다른 분들 코드 보고 좌절 ㅎㅎ; 내 반절로 구현하기도 하고 

stable_sort 라는 것을 쓰신 분도 있더군요. 여기서 A,B 가 같지만 B가 A보다 늦게 나오면 정렬 후에도

순서를 유지해야 한다고 하는데, 아마 알고리즘 수강할 때 배운 안정성인 것 같아요. 

알고리즘 강의 수강 전에도 정렬 알고리즘에 대해 알고는 있었는데, 제자리성과 안정성은 처음 본 개념이었는데 

제자리성은 정렬 알고리즘의 space complexity 를 좌우하는 중요한 요소이고, 안정성은 radix sort, shell sort를 위해

매우 중요한 요소이죠. quick sort 가 특히 인상적이어서 완전히 외어버리겠다 생각하고 엄청 여러 번 짰는데 

지금은 원리는 잘 기억나지만 바로 짜보라고 하면 못 짤 것 같아서 슬프네요 ㅜ

 

<풀이> 

#include <string>
#include <algorithm>
#include <cctype>
#include <iostream>
#include <vector>

using namespace std;

typedef struct file {
    string org; 
    string HEAD;
    int number;
    string tail;
    int index;
}file;

file parse(string raw, int i) {
    string HEAD; 
    int number_start = 0;
    for (int i=0; i < raw.length(); i++) {
        char ch = raw[i];
        if (ch >='0' && ch <= '9') {
            number_start = i;
            break;
        } else {
            HEAD += ch;
        }
    }
    transform(HEAD.begin(), HEAD.end(), HEAD.begin(), 
             [](unsigned char c) { return tolower(c); });
    
    int idx = number_start; int acc = 0; string temp_num = "";
    while (idx < raw.length()) {
        if (acc == 5) break;
        if ((raw[idx] >= '0' && raw[idx] <= '9')) {
            temp_num += raw[idx]; 
            acc++;
            idx++;
        } else {
            break;
        }
    }
    string comp_num(5 - acc, '0'); comp_num += temp_num;
    return file{raw, HEAD, stoi(comp_num), raw.substr(idx), i};
}

bool comp(file& a, file& b) {
    if ((a.HEAD == b.HEAD) && (a.number == b.number)) {
        return a.index < b.index;
    }
    if (a.HEAD == b.HEAD) {
        return a.number < b.number; 
    } else {
        return a.HEAD < b.HEAD;
    }
}

vector<string> solution(vector<string> files) {
    vector<string> answer;
    vector<file> parsed_vec;
    for (int i=0; i < files.size(); i++) {
        string elem = files[i];
        parsed_vec.push_back(parse(elem, i));
    }
    sort(parsed_vec.begin(), parsed_vec.end(), comp);
    for (file f : parsed_vec) {
        answer.push_back(f.org);
    }
    return answer;
}

아쉬운점은, 처음에 성능을 위해서 file struct에 org 부분을 reference 로 했는데, implicit copy 라는 제약조건이 있어서 

하릴없이 그냥 복사 받는 것으로 썼네요. C++ 이 주 언어가 아니다 보니깐, 이런 부분에서 좀 막힙니다.

transform 이란 함수도 배웠습니다. 쓸 일이 많을 것 같아요.

stable_sort 를 알았다면, 마지막에 answer 에 푸시하는 과정을 절약할 수 있었을 것 같네요.