[백준]1431번 시리얼 번호 (sort 함수 응용)

문제

https://www.acmicpc.net/problem/1431

1431번: 시리얼 번호

 

코드

 

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

bool com(string& a, string& b)
{
	int sum_a = 0;
	int sum_b = 0;

	if (a.size() != b.size()) //1. 길이가 다르면 짧은것 먼저
		return a.size() < b.size();

	for (int i = 0; i < a.size(); i++) { //숫자끼리 더함
		if(isdigit(a[i]))//0을 제외한 다른숫자는 true (즉 숫자일때)
			sum_a+=(a[i]-'0');  //문자로 입력된 숫자-> 숫자로 변경
	}
	for (int i = 0; i < b.size(); i++) {
		if (isdigit(b[i]))
			sum_b += (b[i] - '0');
	}

	if (sum_a != sum_b) // 2. 자리수의 합 비교해서 작은합이 먼저
		return sum_a < sum_b;

	return a < b; //3. 두조건으로 비교할수없으면 사전순
}


int main()
{
	int n;
	vector<string> v;
	string s;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		v.push_back(s);
	}
	sort(v.begin(), v.end(), com);

	for (int i = 0; i < n; i++) {
		cout << v[i] << '\n';
	}
}

 

풀이

com 함수를 이용하여 1,2,3번 조건에 맞게 정렬하는것이 목표다.

 

비교함수를 쓸때 헷갈리는게 있는데

오른쪽이 왼쪽보다 크기때문에 오른쪽은 계속 크게 정렬되기때문에 오름차순으로 정렬된다고 생각하면 외우기 편하다.

주의해야할것은 두 값이 같을때(혹은 우선순위가 같을때) 반드시 false 를 반환해야한다. 안그러면 런타임에러가 발생한다.

 

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

각 코드에 대한 설명은 주석에 ~!