[프로그래머스] 파일명 정렬

✔️ 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17686
카카오 기술블로그 문제 해설 : https://tech.kakao.com/2017/11/14/kakao-blind-recruitment-round-3/
2018 카카오 블라인드 채용 3차 코딩테스트 2번 문제다.

✔️ 문제 이해

소스 파일 저장소에 저장된 파일들을 정렬해서 반환하는 문제다.
파일명은 HEAD, NUMBER, TAIL 세 부분으로 구성된다.
HEAD : 숫자가 아닌 문자들로 이루어져 있다. 최소 한 글자 이상이다.
NUMBER : 1 ~ 5 글자 사이의 연속된 숫자로 이루어져 있다.
TAIL : NUMBER 뒤의 나머지 부분으로 여기에는 숫자가 다시 나타날 수도 있으며, 아무 글자도 없을 수 있다.
파일을 아래 기준에 따라 정렬 해야한다.
- 파일명은 우선 HEAD 부분을 기준으로 사전 순으로 정렬한다. HEAD 부분은 문자열 비교시 대소문자 구분을 하지 않는다.
- 파일명의 HEAD 부분이 같을 경우, NUMBER의 숫자 순으로 정렬한다.
- 두 파일의 HEAD 부분과, NUMBER 부분의 숫자도 같을 경우, 원래 입력에서 주어진 순서를 유지한다. MUZI01.zip과 muzi1.png가 입력으로 들어오면, 정렬 후에도 입력 시 주어진 두 파일의 순서가 바뀌어서는 안 된다.
값 범위
- 입력으로 배열 files가 주어진다. files는 1000 개 이하의 파일명을 포함하는 문자열 배열이다.
- 각 파일명은 100 글자 이하 길이다. 파일명은 영문 대소문자, 숫자, 공백(“ ), 마침표(.), 빼기 부호(-“)만으로 이루어져 있다. 파일명은 영문자로 시작하며, 숫자를 하나 이상 포함하고 있다.

✔️ 알고리즘 설계

주어진 파일명 배열을 하나씩 탐색한다.
파일명을 HEAD, NUMBER 부분으로 나눈다. (TAIL은 정렬 기준에 해당하지 않으므로 나누지 않아도 된다.)
파일명, HAED, NUMBER을 하나의 구조체로 묶고 구조체 벡터에 넣는다.
구조체 벡터를 HEAD, NUMBER 기준으로 정렬한다. (HEAD, NUMBER 순으로 정렬되게끔 sort 함수에 정렬 기준 함수를 만들어 인자로 넣는다. )
문제 조건에서 “두 파일의 HEAD 부분과, NUMBER의 숫자도 같을 경우, 원래 입력에서 주어진 순서를 유지한다.” 라고 했다. 이는 stable sort (안정 정렬)을 수행하라는 뜻이다. c++의 sort 함수는 stable sort가 아닌 quick sort로 구현돼있다. merge sort 로 구현된 stable_sort 함수를 사용해서 정렬을 수행 해야한다.

✔️ 상세 구현설명

파일명에서 HEAD를 추출하는 방법 : 파일명을 맨 앞에서부터 탐색 하면서, 숫자가 아닌 문자를 추출한다. HEAD는 비교시 대소문자 구분을 하지 않으므로 tolower 함수 사용하여 문자를 소문자로 변환해서 추출한다.
파일명에서 NUMBER를 추출하는 방법 : HEAD가 끝나고 난 다음 인덱스부터 파일명을 탐색하면서, 숫자 문자만 뽑아낸다. NUBER는 최대 5자리이므로 5자리 이상 추출되면, 중단한다.
파일명, HEAD, NUMBER를 하나의 구조체로 묶고, 구조체 벡터에 넣는다. (NUMBER 문자열은 stoi 함수를 사용해 정수형 숫자로 변환한다.)
주어진 모든 파일명 배열에 대해 위와 같은 작업을 수행하여 구조체 벡터를 만들고, 구조체 벡터를 stable_sort 함수를 사용해서 안정정렬 한 뒤 구조체 벡터에서 파일명만 따로 추출하여 결과 벡터에 넣고 반환한다.

👨🏻‍💻 소스 코드

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

typedef struct {
	string name; // 파일명
	string head;  // HAED
	int number; // NUMBER
}fileData;

// 정렬 기준 함수 (HEAD, NUMBER 순서로 정렬)
bool comp(fileData a, fileData b) { 
	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<fileData> fileDatas;

	for (int i = 0; i < files.size(); i++) {
		string head="", number = "";
		int idx;

		for (int j = 0; j < files[i].size(); j++) {

			if (isdigit(files[i][j])) { // 숫자라면, HEAD가 끝났다는 뜻.
				idx = j; // 인덱스를 저장한다.
				break;
			}

			// HEAD 추출 : 대소문자 구분을 하지 않으므로, 모두 소문자로 변환하여 추출.
			head += tolower(files[i][j]); 
		}

		for (int j = idx; j < files[i].size(); j++) {

			// 숫자가 아니거나 5자리 이상이면, 중단.
			if (!isdigit(files[i][j]) || number.size() >= 5) {
				break;
			}

			// NUMBER 추출
			number += files[i][j]; 
		}

		// 파일명, HEAD, NUMBER을 구조체로 묶고, 구조체 배열에 넣는다.
		fileDatas.push_back({ files[i], head, stoi(number) });
	}
	
	// HEAD, NUMBER 순서로 stable sort를 수행한다.
	stable_sort(fileDatas.begin(), fileDatas.end(), comp);

	// 구조체에서 파일명만 추출하여 결과 벡터에 넣어준다.
	for (int i = 0; i < fileDatas.size(); i++)
		answer.push_back(fileDatas[i].name);

	return answer; // 결과 반환.
}

✔️ 복기해야 할 지식

안정 정렬, 정렬 기준 함수 (수정 예정)

✔️ 문제 회고

문제 조건에 맞추어 어렵지 않게 구현했지만, stable sort 를 해야하는 것을 간과했다.
c++ 의 stable_sort 를 처음 알게됐다.

Byung Wook Park (박병욱)

✔️ 문제

✔️ 문제 이해

✔️ 알고리즘 설계

✔️ 상세 구현설명

👨🏻‍💻 소스 코드

✔️ 복기해야 할 지식

✔️ 문제 회고