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

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

문제 링크

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

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

---

C++ 풀이

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

struct separated_names
{
	string HEAD, ORIGINAL_NAME;
	int NUMBER;
};

bool cmp(separated_names a, separated_names b) {
	if (a.HEAD != b.HEAD) //HEAD가 다른 경우 HEAD 사전순 정렬
		return a.HEAD < b.HEAD;
	else //HEAD가 같은 경우 NUMBER 크기순 정렬
		return a.NUMBER < b.NUMBER;
}

vector<string> solution(vector<string> files) {
	vector <separated_names> separated_names(files.size());
	for (int i = 0; i < files.size(); i++) {
		int j = 0;
		while (!isdigit(files[i][j])) j++;
		int k = j;
		while (isdigit(files[i][k])) {
			k++;
			if (k - j >= 5) //NUMBER는 최대 5자리
				break;
		}
		separated_names[i].ORIGINAL_NAME = files[i]; //기존 파일명 저장
		transform(files[i].begin(), files[i].begin() + j, files[i].begin(), ::toupper); //대문자로 변환
		separated_names[i].HEAD = files[i].substr(0, j); //숫자 전까지의 string을 HEAD에 저장
		separated_names[i].NUMBER = stoi(files[i].substr(j, k - j)); //첫 연속된 숫자를 NUMBER에 저장
	}

	stable_sort(separated_names.begin(), separated_names.end(), cmp); //안정 정렬

	vector <string> answer;
	for (int i = 0; i < separated_names.size(); i++)
		answer.push_back(separated_names[i].ORIGINAL_NAME);

	return answer;
}

처음 문제 풀이할 때는 sort를 사용하여 작성했었다. 하지만 테스트케이스 3번부터 전부 오답 처리가 되었었다.

 

분명 빼먹은 조건 처리는 없어보이는데 무엇이 문제일까... 하고 한참 댓글들과 다른 분들의 블로그를 참고한 결과, sort가 불안정 정렬임을 알게되었다. 불안정 정렬의 경우, 정렬 시 두 개의 값이 같은 값일 때 두 값의 순서가 바뀔 수도, 안바뀔 수도 있다는 것이다. 즉, sort를 사용하면 문제의 세번 째 조건인 "두 파일의 HEAD 부분과, NUMBER의 숫자도 같을 경우, 원래 입력에 주어진 순서를 유지한다." 를 항상 만족하지는 않는다는 것이다. 

 

하지만 stable_sort의 경우, 안정 정렬이기 때문에 두 개의 값이 같은 값일 때 순서가 바뀌지 않음이 보장된다.

이를 알고 나서 sort 대신 stable_sort를 사용하여 테스트케이스들을 통과할 수 있었다. 배울 것이 많다.