시리얼 번호 - 백준 1431

문자열을 정렬하는 문제입니다.

 

문제 링크

1431번: 시리얼 번호 (acmicpc.net)

1431번: 시리얼 번호

이 문제의 요건 역시 정렬 조건입니다.  C++ 의 STL을 사용하여 정렬합시다.

 

정렬 조건

1. A와 B의 길이가 다르면, 짧은 것이 먼저 온다.
2. 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)
3. 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.

 

소스코드

#include<iostream>
#include <algorithm>
#include<string>
using namespace std;
string s[50];

int getSum(string a) {
	int temp = 0;

	for (int i = 0; i < a.length(); i++) {
		if (a[i] >= '0' && a[i] <= '9')
			temp += a[i] - '0';
	}
	return temp;
}

bool compare(string a, string b) {
	if (a.length() != b.length())  // 길이가 다른 경우
		return a.length() < b.length();
	else { // 길이가 같은 경우
		int sumA = getSum(a);
		int sumB = getSum(b);
		if (sumA != sumB)
			return sumA < sumB;
		else {
			return a < b;
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N; cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> s[i];
	}

	sort(s, s + N, compare);
	for (int i = 0; i < N; i++) {
		cout << s[i] << endl;
	}

	return 0;
}

 

중요한 부분은 compare 함수입니다. sort 함수의 정렬방식을 정의해줍니다.

우선 문제 조건을 그대로 대입하면 됩니다. 길이가 다른 경우에는 짧은 순으로 정렬 (a.length() < b.length())

왼쪽의 길이가 오른쪽의 길이보다 짧도록 정렬한다는 뜻이됩니다. (왼쪽이 오른쪽에 비해서 가 기준이 된다.)

 

길이가 같은 경우 숫자만 더해서 그 값이 작은 순으로 정렬해줍니다. (sumA < sumB )

그것도 아니라면 사전순으로 정렬합니다. ( a < b)