[Programmers]2018 KAKAO BLIND RECRUITMENT: [3차] 파일명 정렬(C++)

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

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

이때까지 외워서 사용했던 정렬 comparator에 대해 생각하게 해주는 문제

카카오 2018년 기출은 풀면서 배워가는게 많은 것 같다

 

파일명 정렬에서는 파일 이름 string을 HEAD, NUMBER, TAIL 세 파트로 나눈 뒤 각각의 order에 따라 정렬을 해주어야 한다.

문자열 토큰화가 크게 복잡하지 않았기 때문에 C++로 풀이했다.

처음 설계했던 풀이

하지만 아무리 해도 테케 20개중에 2개만 통과돼서 머리가 아팠는데 두 가지를 추가해주고 솔브할 수 있었다.

1️⃣ stable_sort()

출처: https://tech.kakao.com/2017/11/14/kakao-blind-recruitment-round-3/

stable sort라는 알고리즘 용어를 처음 알게 되었다. stable sort가 적용되면 swap연산 시 같은 key값인 element에 대해서는 기존의 순서가 유지되고, unstable sort인 경우에는 그것을 보장하지 않는다.

마침 C++의 algorithm 라이브러리에 stable_sort() 함수를 지원한다는 것을 알게 되어서 적용할 수 있었다. 

2️⃣ a.compare(b)

HEAD section에서 사전순 정렬을 해야하는데, 기존에 내가 알던 방식으로는 ascii code 기준 정렬밖에 할 수 없었다. 그래서 찾아보던 중 string class의 compare 함수를 알게 되었다.

• 함수의 return 값이 0일 경우: a string과 b string이 동일하다
• 함수의 return 값이 0보다 작을 경우: a string이 b string보다 lexical order가 앞선다.
• 함수의 return 값이 0보다 클 경우: b string이 a string보다 lexical order가 앞선다.

 

또한 compare 함수의 return값이 true일 경우 오름차순, false일 경우 내림차순으로 정렬을 하기 때문에 위의 성질들을 고려할 수 있게끔 코딩해주었다.

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

typedef struct {
	string HEAD;
	string NUMBER;
	string TAIL;
}file;

bool cmp(file A, file B) {
	string lowA = A.HEAD, lowB = B.HEAD;
	transform(lowA.begin(), lowA.end(), lowA.begin(), ::tolower);
	transform(lowB.begin(), lowB.end(), lowB.begin(), ::tolower);
	if (lowA.compare(lowB) != 0)return lowA.compare(lowB)<0;

	int numA = stoi(A.NUMBER);
	int numB = stoi(B.NUMBER);
	return numA < numB;
}

vector<string> solution(vector<string> files) {
	vector<string> answer;
	vector<file> v;

	for (auto f:files) {
		v.push_back({ "","","" });
		int idx = 0, n = 0;
		for (int i = 0; i < f.length();i++) {
			switch (idx) {
			case 0:
				if (isdigit(f[i])) {
					i--; idx = 1; break;
				}
				v.back().HEAD.push_back(f[i]);
				break;
			case 1:
				if (!isdigit(f[i])||n>=5) {
					i--; idx = 2; break;
				}
				if(f[i]!=0&&n!=0)n++;
				v.back().NUMBER.push_back(f[i]);
				break;
			case 2:
				v.back().TAIL.push_back(f[i]);
				break;
			}
		}
	}

	stable_sort(v.begin(), v.end(), cmp);
	
	for (auto str : v) {
		answer.push_back(str.HEAD + str.NUMBER + str.TAIL);
	}
	return answer;
}