백준 1431 c++ "시리얼 번호" -PlusUltraCode-

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

[필자 사고]

자료구조를 이용하여 정렬 알고리즘을 이용해서 푸는 문제이다.

정렬 알고리즘을 따로 정의해야 되서 학습에 많은 도움이 되었다ㅏ.

[코드 해설]

1. 구조체 정의 및 우선순위 큐 정렬 기준 설정

이 프로그램은 문자열을 입력받아 특정 기준에 따라 정렬된 순서로 출력하는 기능을 한다. 이를 위해 먼저 Node라는 구조체를 정의한다. 각 Node는 세 가지 정보를 담고 있다:

• str: 원본 문자열
• size: 문자열의 길이
• sumNumber: 문자열 내 숫자의 합

그리고 이 구조체를 정렬하기 위한 사용자 정의 비교 함수 cmp를 구현한다. 정렬 기준은 다음과 같다:

1. 문자열 길이가 짧을수록 우선순위가 높다.
2. 길이가 같을 경우, 문자열 내 숫자의 합이 작은 것이 우선이다.
3. 위의 조건까지 같다면, 사전순으로 빠른 문자열이 우선이다.

---

2. 숫자 합 계산 함수 (Sum_Jarisu 함수)

Sum_Jarisu 함수는 문자열을 받아서, 해당 문자열에 포함된 숫자(문자형 숫자 '0'~'9')의 합을 계산해 반환한다. 이 값은 이후 정렬 기준 중 하나로 사용된다.

---

3. 입력 처리 및 정렬 출력 (Input 함수)

Input 함수는 다음의 기능을 수행한다:

1. 사용자로부터 정수 N을 입력받는다. 이는 입력받을 문자열의 개수이다.
2. N번 반복하여 문자열을 입력받고, 각 문자열에 대해 다음 작업을 수행한다:
   • 문자열 길이를 계산한다.
   • 문자열 내 숫자의 합을 Sum_Jarisu 함수를 통해 구한다.
   • 이를 바탕으로 Node 구조체를 생성하고, 우선순위 큐에 삽입한다.
3. 모든 문자열이 입력되어 우선순위 큐에 저장된 후, 큐에서 하나씩 꺼내면서 정렬된 순서대로 출력한다.

 

[소스 코드]

#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;

typedef struct Node {
	string str;
	int size;
	int sumNumber;
};
struct cmp {
	bool operator()(Node a, Node b) {
		if (a.size == b.size && a.sumNumber == b.sumNumber) {
			return a.str > b.str;
		}
		if (a.size == b.size) {
			return a.sumNumber > b.sumNumber;
		}
		return a.size > b.size;
	}
};

int N;
priority_queue<Node, vector<Node>, cmp> pq;

int Sum_Jarisu(string str) {
	int resultSum = 0;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] >= '0' && str[i] <= '9') {
			resultSum += str[i] - '0';
		}
	}

	return resultSum;
}

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		string str;
		cin >> str;
		int sumNumber = Sum_Jarisu(str);
		Node node = { str,str.size(),sumNumber };
		pq.push(node);
	}

	while (!pq.empty()) {
		cout << pq.top().str << '\n';
		pq.pop();
	}
}

int main(void) {
	Input();
}