[Programmers Level2] [3차] 파일명 정렬(C++)

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

[문제 풀이 사이트]

 

 

프로그래머스

 

 

[문제 설명]

 

세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다.

저장소 서버에는 프로그램의 과거 버전을 모두 담고 있어, 이름 순으로 정렬된 파일 목록은 보기가 불편했다. 파일을 이름 순으로 정렬하면 나중에 만들어진 ver-10.zip이 ver-9.zip보다 먼저 표시되기 때문이다.
버전 번호 외에도 숫자가 포함된 파일 목록은 여러 면에서 관리하기 불편했다. 예컨대 파일 목록이 ["img12.png", "img10.png", "img2.png", "img1.png"]일 경우, 일반적인 정렬은 ["img1.png", "img10.png", "img12.png", "img2.png"] 순이 되지만, 숫자 순으로 정렬된 ["img1.png", "img2.png", "img10.png", img12.png"] 순이 훨씬 자연스럽다.
무지는 단순한 문자 코드 순이 아닌, 파일명에 포함된 숫자를 반영한 정렬 기능을 저장소 관리 프로그램에 구현하기로 했다.

소스 파일 저장소에 저장된 파일명은 100 글자 이내로, 영문 대소문자, 숫자, 공백(" "), 마침표("."), 빼기 부호("-")만으로 이루어져 있다. 파일명은 영문자로 시작하며, 숫자를 하나 이상 포함하고 있다.
파일명은 크게 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가 입력으로 들어오면, 정렬 후에도 입력 시 주어진 두 파일의 순서가 바뀌어서는 안 된다.

무지를 도와 파일명 정렬 프로그램을 구현하라.

[입력 형식]

 

입력으로 배열 files가 주어진다.

• files는 1000 개 이하의 파일명을 포함하는 문자열 배열이다.
• 각 파일명은 100 글자 이하 길이로, 영문 대소문자, 숫자, 공백(" "), 마침표("."), 빼기 부호("-")만으로 이루어져 있다. 파일명은 영문자로 시작하며, 숫자를 하나 이상 포함하고 있다.
• 중복된 파일명은 없으나, 대소문자나 숫자 앞부분의 0 차이가 있는 경우는 함께 주어질 수 있다. (muzi1.txt, MUZI1.txt, muzi001.txt, muzi1.TXT는 함께 입력으로 주어질 수 있다.)

 

[출력 형식]

 

위 기준에 따라 정렬된 배열을 출력한다.

 

[입출력 예]

 

#입출력 예1
입력: ["img12.png", "img10.png", "img02.png", "img1.png", "IMG01.GIF", "img2.JPG"]
출력: ["img1.png", "IMG01.GIF", "img02.png", "img2.JPG", "img10.png", "img12.png"]

#입출력 예2
입력: ["F-5 Freedom Fighter", "B-50 Superfortress", "A-10 Thunderbolt II", "F-14 Tomcat"]
출력: ["A-10 Thunderbolt II", "B-50 Superfortress", "F-5 Freedom Fighter", "F-14 Tomcat"]

 

[문제 풀이]

 

문제에 소개된 대로 파일명을 HEAD, NUMBER, TAIL 3가지로 분리해야 한다.

나는 파일명을 분리하기 위해 tuple을 사용했다.
tuple의 첫번째 인자는 HEAD를 의미, 두번째 인자는 NUMBER을 의미, 세번째 인자는 TAIL을 의미하도록 했다.

아래와 같이 분리하고 각 tuple을 vector 배열에 추가하였다.

tuple이 추가된 vector 배열을 정렬해야하는데

• 두 파일의 HEAD 부분과, NUMBER의 숫자도 같을 경우, 원래 입력에 주어진 순서를 유지한다. MUZI01.zip과 muzi1.png가 입력으로 들어오면, 정렬 후에도 입력 시 주어진 두 파일의 순서가 바뀌어서는 안 된다.

위 조건으로 인해 동일한 값의 요소들에 대해, 두 요소가 기존에 가지고 있던 순서를 보장하는 stable_sort 함수를 사용했고, 정렬의 조건은 사용자 정의 함수로 따로 코드를 작성했다.

정렬을 위한 사용자 정의 함수는 아래와 같은 알고리즘으로 작성했다.

1. 대소문자를 구분하지 않기 때문에 모두 대문자로 통일하여 HEAD를 확인

1-1. HEAD가 같다면 NUMBER을 string을 int형으로 변환하여 확인
1-1-1. NUMBER가 같다면 입력 순서를 유지하여 정렬
1-1-2. NUMBER가 다르다면 NUMBER 숫자 순으로 정렬

1-2. HEAD가 다르다면 사전순으로 정렬
정렬 후 각 tuple의 0번째, 1번째, 2번째 string을 합쳐서 정답 배열에 추가해주면 된다.

[최종 코드]

 

[GitHub]

 

 

GitHub - SmallPeanutPark/Programmers: Study Programmers for Coding Test

 

 

#include <string>
#include <vector>
#include <tuple>
#include <iostream>
#include <algorithm>
using namespace std;

vector<tuple<string, string, string>> t; // HEAD, NUMBER, TAIL

void divideStr(string str) {
    string plus[3]; // HEAD, NUMBER, TAIL
    int idx = 0;
    int numbercnt = 5;
    bool isEnd = false; // TAIL 구분
    for(char element : str) {
        if(isalpha(element)) {
            // HEAD: 문자로 이루어짐, 최소한 1글자 이상
            // isalpha 알파벳 문자인경우
            if(isEnd) {
                idx = 2;
            } else {
                idx = 0;
            }
            plus[idx] += element;
        } else {
            if((idx == 2) && (isdigit(element))) {
                idx = 2;
            } 
            else if(isdigit(element)) {
                // NUMBER : 0 ~ 99999 사이의 숫자
                if(numbercnt > 0) {
                    idx = 1;
                    numbercnt -= 1;
                    isEnd = true;
                } else {
                    idx = 2;
                }
            } else {
                if(isEnd) idx = 2;
                else idx = 0;
            }
            plus[idx] += element;
        }
    }
    // HEAD, NUMBER, TAIL 3부분으로 나누어 tuple화 시켜 vector에 저장
    tuple<string, string, string> temp(plus[0], plus[1], plus[2]);
    t.emplace_back(temp);
}

void calculateHeadNumberTail(vector<string> s, int gSize) {
    for(int i = 0; i < gSize; ++i) {
        divideStr(s[i]); // HEAD, NUMBER, TAIL 분리하는 함수
    }
}

// HEAD 부분을 기준으로 사전 순으로 정렬, 대소문자 구분하지 않음
// 대소문자 차이외에 같은 경우 NUMBER 순으로 정렬 숫자 앞의 0은 무시되고 012, 12 같은 값임
// HEAD, NUMBER 숫자도 같은 경우 입력에서 주어진 순서 유지

bool cmp(const tuple<string, string, string> t1, const tuple<string, string, string> t2) {
    string a = get<0>(t1);
    transform(a.begin(), a.end(), a.begin(), ::toupper);

    string b = get<0>(t2);
    transform(b.begin(), b.end(), b.begin(), ::toupper);
    if(a.compare(b) == 0) {
        // HEAD 같은 경우, NUMBER 순으로 정렬
        int num1 = stoi(get<1>(t1));
        int num2 = stoi(get<1>(t2));
        if(num1 == num2) {
            // NUMBER도 같다면 주어진 순서를 유지
            return false;
        } else {
            // NUMBER 같지 않을 때
            if(num1 < num2) {
                return true;
            } else {
                return false;
            }
        }
    } else {
        // HEAD 다른 경우, 사전 순으로 정렬
        return a < b;
    }
}

vector<string> solution(vector<string> files) {
    int gSize = files.size();
    calculateHeadNumberTail(files, gSize);

    // 정렬
    stable_sort(t.begin(), t.end(), cmp);
    vector<string> answer;
    for(int i = 0; i < gSize; ++i) {
        string gStr = get<0>(t[i]);
        gStr += get<1>(t[i]);
        gStr += get<2>(t[i]);
        answer.emplace_back(gStr);
    }
    return answer;
}