백준1431 - 시리얼 번호

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

1431번: 시리얼 번호

algorithm 라이브러리에 sort를 이용하는 문제다.

 

algorithm 라이브러리에 sort는 퀵정렬을 기반으로 정렬한다.

따라서 평균 복잡도는 O(nlog2n)이 나오지만 최악의 경우 O(n^2)이 나오게 된다.

문제에서는 최대 입력 갯수를 10^3으로 주었기 때문에 최악의 경우 10^6이 나온다. (백준에서는 대략적으로 자료형 10^8개를 1초로 가정한다.) 따라서 sort를 이용하더라도 정렬 기준이 복잡하지 않다면 시간초과가 나지 않는다.

 

sort는 sort(시작하는 구간, 끝나는 구간, 정렬 기준)형식으로 구현한다.

 

문제에서 주어진대로 함수를 만든 뒤 함수를 sort에 세번째 인자로 사용하여 정렬한다.

 

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

//sort의 기준으로 삼을 함수
bool compare(string s1, string s2) {
	if (s1.size() < s2.size()) { //s1의 길이가 s2보다 작을 때
		return true;
	}
	else if (s1.size() == s2.size()) { //s1과 s2의 길이가 같을 때
		int sum1 = 0, sum2 = 0; //s1과 s2의 들어있는 숫자를 더하여 저장할 변수

		//s1의 있는 숫자를 모두 더한다.
		for (int i = 0; i < s1.size(); i++) {
			if ('0' <= s1[i] && s1[i] <= '9') {
				sum1 = sum1 + (s1[i] - '0');
			}
		}
		//s2의 있는 숫자를 모두 더한다.
		for (int i = 0; i < s2.size(); i++) {
			if ('0' <= s2[i] && s2[i] <= '9') {
				sum2 = sum2 + (s2[i] - '0');
			}
		}
		if (sum1 < sum2) { //s1의 숫자가 s2의 숫자보다 작으면
			return true;
		}
		else if (sum1 == sum2) { //s1의 숫자가 s2의 숫자와 같으면
			if (s1 < s2) { //s1이 s2보다 사전순으로 앞에 오면
				return true;
			}
			else { //s1이 s2보다 사전순으로 뒤에 오면
				return false;
			}
		}
		else { //s1의 숫자가 s2의 숫자보다 크면
			return false;
		}
	}
	else { //s1의 길이가 s2보다 길 때
		return false;
	}
}

int main() {
	int n; //입력할 문자열의 수
	vector<string> v; //입력할 문자열들을 저장할 공간
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		v.push_back(s);
	}
	sort(v.begin(), v.end(), compare); //sort를 이용하여 정렬
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << '\n';
	}
}