[알고리즘] 백준 1431번 문제_시리얼 번호

시리얼 번호 정렬 :https://www.acmicpc.net/problem/1431

================================== 풀이 ====================================

C++ 함수 사용

#include <iostream>   // C++ 헤더
#include <algorithm>  // STL 라이브러리 -> sort() 함수가 정의되어있음
#include <string>
#include <vector>

using namespace std;

string a[20000];
int n;

int getSum(string a) {

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

bool compare(string a, string b) {

	if (a.length() < b.length()) {
		return 1;
	}
	else if ( a.length() > b.length()){
		return 0;
	}
// 길이가 같은 경우
	else {
		int aSum = getSum(a);
		int bSum = getSum(b);
		if (aSum != bSum) {
			return aSum < bSum;
		}
		else {
			return a < b;
		}
	}
}

int main(void) {   

	cin >> n;  // n 입력
	for (int i = 0; i < n; i++) {
		cin >> a[i];      // 단어 입력
	}

	sort(a, a + n, compare);  // a에서 시작, a+n까지 진행
	for (int i = 0; i < n; i++) {
		if (i > 0 && a[i] == a[i - 1]) {
			continue;
		}
		else {
			cout << a[i] << '\n';
		}
		
	}
}

​

힙 정렬

import java.util.Scanner;

public class Main {

	static Scanner s = new Scanner(System.in);
	
	public static void main(String[] args) {
		
		int num = s.nextInt();
		int root, cmp;
		String tmp;
		String[] list = new String[num];
		
		for(int i = 0; i < num;  i++) 
			list[i] = s.next();
		
		for(int i = 1; i < num; i++) {
			cmp = i;
			
			do {
				root = (cmp -1) / 2;
				if(compare(list[root],list[cmp])) {
					tmp = list[root];
					list[root] = list[cmp];
					list[cmp] = tmp;
				}
				
				cmp = root;			
			} while (cmp != 0);
		}
		
		for(int i = num-1; i >= 0; i--) {
			tmp = list[0];
			list[0] = list[i];
			list[i] = tmp;
			
			root = 0;
			do {
				cmp = root * 2 + 1;
				if(cmp < i -1 && compare(list[cmp],list[cmp+1]))
					cmp++;
				
				if(cmp < i && compare(list[root],list[cmp])) {
					tmp = list[root];
					list[root] = list[cmp];
					list[cmp] = tmp;
				}
				
				root = cmp;
			}while (cmp < i);
		}
		
		for(String i : list)
			System.out.println(i);
	}
	
	static boolean compare(String a, String b) { // a : root , b : cmp
		
		int[] comp = {0,0};
		
		if(a.length() < b.length())
			return true;
		
		else if(a.length() == b.length()) {
			
			for(int i = 0; i < a.length();i++) {
				
				if(Character.isDigit(a.charAt(i)))
					comp[0] += Integer.parseInt(a.charAt(i) + "");
				
				if(Character.isDigit(b.charAt(i)))
					comp[1] += Integer.parseInt(b.charAt(i) + "");
			}
			
			if(comp[0] < comp[1])
				return true;
			
			else if( comp[0] > comp[1])
				return false;
			
			else {
				for(int i = 0; i < a.length(); i ++) {
					if(a.charAt(i) < b.charAt(i))
						return true;
					else if(a.charAt(i) > b.charAt(i))
						return false;
				}
				return false;
			}
		}
		else {
			return false;
		}
	}
}