문제

Programmers [3차] 파일명 정렬

핵심

• 입력의 크기가 1,000이라 구현에 초점을 맞춘다.
• 파일명이 크게 HEAD, NUMBER, TAIL로 이루어져 있을 때 HEAD를 기준으로 사전 순으로 정렬하고(대소문자 구분 X) NUMBER 숫자 순으로 정렬한다. 이때, 숫자 앞의 0은 무시한다. (012와 12는 같은 숫자이다)
• 처음 접근할 때는 head, number, tail로 나누었을 때 head로 정렬하고 나서 number를 붙이고, number를 기준으로 다시 재정렬할 때 number를 기준으로 재정렬하고 싶은데 이미 문자열이 합쳐졌으니 어떻게 처리할지 까다로웠다.
• 구조체를 사용하면 미리 파싱하고, 정렬 함수를 이용해 한 번에 정렬하면 구현이 굉장히 간단해진다. 구조체에는 head, number 그리고 초기 순서를 저장한다.

vector<tuple<string, int, int>> f; // head, number, turn

1. head와 number로 나누기

void detach(int index, string& file_name) {
    
    string h = "";
    int i = 0;
    for (; i < file_name.length(); ++i) {
        if (file_name[i] >= '0' && file_name[i] <= '9') {
            break;
        }
        if (file_name[i] >= 'A' && file_name[i] <= 'Z') {
            h += file_name[i] - 'A' + 'a';
            continue;
        }  
        h += file_name[i];
    }
    string n = "";
    for (; i < file_name.length(); ++i) {
        if (!(file_name[i] >= '0' && file_name[i] <= '9')) break;
        if (n.length() >= 5) break;
        n += file_name[i];
    }
    f.push_back({h, stoi(n), index});
}

• detach 함수에서 숫자가 나오기 전까지 head에 저장한다. 초기 인덱스를 저장하므로 대문자인 경우 바로 소문자로 변경한다.
• 숫자가 나오기 시작하면 number에 저장한다. 최대 다섯 글자 사이의 연속된 숫자이므로, 5개가 넘어가면 루프를 종료한다. 이 뒤에는 tail로 보는 데 문제에서 tail로 정렬하는 부분이 없기 때문에 따로 저장하지 않았다.

2. 정렬 함수 작성하기

sort(f.begin(), f.end(), [](auto& a, auto& b) {
	string h1 = get<0>(a);
	string h2 = get<0>(b);
	
	int n1 = get<1>(a);
	int n2 = get<1>(b);
	
	if (h1 == h2) {
		return n1 < n2;
	} else {
		return h1 < h2;
	}
});

• 초기에 작성한 정렬 함수인데, 테스트 케이스는 통과했지만 채점해 보면 거의 다 틀린다. 뭐가 문제일까? head가 같을 때 number 기준으로 정렬하지만, number가 같다면 c++ sort는 stable_sort가 아니기 때문에 기존 순서를 유지하지 않는다!
• stable_sort를 쓰거나 또는 n1과 n2가 같을 때 초기 인덱스 오름차순으로 다시 정렬해 주어야 한다.

// stable_sort
stable_sort(f.begin(), f.end(), [](auto& a, auto& b) {...}

// 정렬 기준 추가
if (h1 == h2) {
	if (n1 == n2) {
		return idx1 < idx2;
	}
	return n1 < n2;
} else {
	return h1 < h2;
}

개선

코드

C++

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

using namespace std;

vector<tuple<string, int, int>> f; // head, number, turn

void detach(int index, string& file_name) {
    
    string h = "";
    int i = 0;
    for (; i < file_name.length(); ++i) {
        if (file_name[i] >= '0' && file_name[i] <= '9') {
            break;
        }
        if (file_name[i] >= 'A' && file_name[i] <= 'Z') {
            h += file_name[i] - 'A' + 'a';
            continue;
        }  
        h += file_name[i];
    }
    string n = "";
    for (; i < file_name.length(); ++i) {
        if (!(file_name[i] >= '0' && file_name[i] <= '9')) break;
        if (n.length() >= 5) break;
        n += file_name[i];
    }
    f.push_back({h, stoi(n), index});
}

vector<string> solution(vector<string> files) {
    
    for (int i = 0; i < files.size(); ++i) {
        detach(i, files[i]);
    }
    
    stable_sort(f.begin(), f.end(), [](auto& a, auto& b) {
        string h1 = get<0>(a);
        string h2 = get<0>(b);

        int n1 = get<1>(a);
        int n2 = get<1>(b);
        
        int idx1 = get<2>(a);
        int idx2 = get<2>(b);
        if (h1 == h2) {
            return n1 < n2;
        } else {
            return h1 < h2;
        }
    });
    
    vector<string> ans;
    for (auto e : f) {
        ans.push_back(files[get<2>(e)]);
    }
    return ans;
}

Java

import java.util.*;

class Solution {
    static class F {
        String head;
        int number;
        int index;
        
        F(String head, int number, int index) {
            this.head = head;
            this.number = number;
            this.index = index;
        }
    }
    
    List<F> fileList = new ArrayList<>();
    
    private void detach(int index, String fileName) {
        StringBuilder head = new StringBuilder();
        int i = 0;
        while (i < fileName.length() && !Character.isDigit(fileName.charAt(i))) {
            head.append(Character.toLowerCase(fileName.charAt(i)));
            i++;
        }
        
        StringBuilder number = new StringBuilder();
        while (i < fileName.length() && Character.isDigit(fileName.charAt(i)) && number.length() < 5) {
            number.append(fileName.charAt(i));
            i++;
        }
        
        fileList.add(new F(head.toString(), Integer.parseInt(number.toString()), index));
    }
    
    public String[] solution(String[] files) {
        
        for (int i = 0; i < files.length; ++i) {
            detach(i, files[i]);
        }
        
        fileList.sort((a, b) -> {
            int headCompare = a.head.compareTo(b.head);
            if (headCompare == 0) {
                return Integer.compare(a.number, b.number);
            }
            return headCompare;
        });
        
        String[] answer = new String[files.length];
        for (int i = 0; i < fileList.size(); ++i) {
            answer[i] = files[fileList.get(i).index];
        }
        return answer;
    }
}