Boj1431_시리얼번호

Published: by Creative Commons Licence

백준 1431 시리얼번호

  • compare 함수를 따로 만들어 줘야함. 구조체를 이용하여 quick_sort 로 문제 해결!

  • 극강의 귀찮은 정렬문제..

  • quick sort 사용시 compare(a,b) 에서 a,b 같을시 return false 해줘야함!


#include<iostream>
using namespace std;
int n;
struct Node {
	int len;
	int sum;
	char c[55];
};
Node node[1000];

void mySwap(Node &a, Node &b) {
	Node newnode = a;
	a = b;
	b = newnode;
}

bool cmp(Node *a, Node *b) {//a<b : true
	if (a->len != b->len) return a->len < b->len;
	else if (a->sum != b->sum) return a->sum < b->sum;
	else {
		for (int i = 0; i < a->len; i++) {
			if ('0' <= a->c[i] && a->c[i] <= '9') {
				if ('0' <= b->c[i] && b->c[i] <= '9') {
					if (a->c[i] == b->c[i]) continue;
					else return a->c[i] < b->c[i];
				}
				else return true;
			}
			else {
				if ('0' <= b->c[i] && b->c[i] <= '9') return false;
				else {
					if (a->c[i] == b->c[i]) continue;
					else return a->c[i] < b->c[i];
				}
			}
		}
	}
	return false;
}


void qs(int s, int e) {
	if (s >= e) return;
	int mid = (s + e) / 2;
	mySwap(node[s], node[mid]);
	int i = s, j = e;
	Node pivot = node[s];
	while (i < j) {
		while (cmp(&pivot, &node[j])) 
			j--;
		while (i < j && !cmp(&pivot, &node[i])) i++;
		mySwap(node[i], node[j]);
	}
	mySwap(node[i], node[s]);
	qs(s, i - 1);
	qs(i + 1, e);
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%s", node[i].c);
		int size = 0, sum = 0;
		for (int j = 0; node[i].c[j]; j++) {
			size++;
			if ('0' <= node[i].c[j] && node[i].c[j] <= '9') sum += (node[i].c[j] - '0');
		}
		node[i].len = size;
		node[i].sum = sum;
	}

	qs(0, n - 1);

	for (int i = 0; i < n; i++) {
		printf("%s\n", node[i].c);
	}
}