백준 1431번: 시리얼 번호

문제

[BOJ][C++] 백준 1920번: 수 찾기

문제는 링크를 클릭해서 볼 수 있다.

풀이

stl sort 함수에 compare 함수를 직접 정의해 시리얼 번호를 정렬했다. compare 함수에서 시리얼 번호를 정렬하는 기준은 크게 둘로 나누었다. a와 b의 길이가 다른 경우와 같은 경우.

첫 번째 a와 b의 길이가 다른 경우, a와 b의 길이를 .length()로 구한 뒤 두 길이의 비교값을 반환했다.

두 번째 a와 b의 길이가 같은 경우, get_integer_sum 함수로 a와 b의 자리수 합을 구했다. get_integer_sum 함수는 문자열에서 숫자만 골라내어 그 합을 구하는 함수이다. 구한 두 자리수의 합이 서로 다르다면 두 자리수의 합 비교값을 반환하고, 같다면 a, b 자체 비교값을 반환했다.

공부

sort()

특징

• < algorithm > 헤더를 선언해야 한다.
• unstable sort이다.
  *값이 같을 때 상대적인 순서를 기억하지 않는다.
• intro sort 알고리즘으로 평균 시간 복잡도는 O(n logn) 이다.
  *intro sort는 quick sort를 기반으로 heap sort와 insertion sort를 혼합된 정렬 알고리즘이다.

기본 형태

기본 형태는 sort(start, end)이다. start 이상 end 미만의 범위, [start, end) 에 있는 인자를 정렬한다.

• 배열의 경우, start에 (배열의 포인터)를 넣고, end에 (배열의 포인터 + 배열의 크기값)을 넣는다.
• 벡터의 경우, start에 v.begin(), end에 v.end()를 넣는다.

// 원형
template <typename T>
void sort(T start, T end, Compare comp);

// 기본 array
sort(arr, arr + n);

// vector
sort(v.begin(), v.end());

정렬 방법

정렬 방법은 오름차순, 내림차순 그리고 사용자가 정렬 조건을 직접 정의하는 방법이 있다. default 값은 오름차순이다.

• 오름차순 / 내림차순

// 오름차순 (Ascending order)
sort(v.begin(), v.end(), less<자료형>());
sort(v.begin(), v.end());                        // default -> less<자료형>() 생략 가능

// 내림차순 (Descending order)
sort(v.begin(), v.end(), greater<자료형>());

• 사용자 정의 함수 compare을 기준으로 정렬할 수도 있다.

sort(v.begin(), v.end(), compare);                // 사용자 정의 함수 사용

문자열에서 숫자 자리수의 합 구하기

for 문을 돌면서 문자가 숫자인 경우 sum에 그 숫자를 더해 자리수의 합을 구했다.

문자열에서 숫자만 골라내기 위해 아스키 코드값을 비교했다. 문자의 아스키 코드값이 ‘0’과 ‘9’의 아스키 코드값 사이에 있다면 숫자로 인식했다. 숫자로 인식한 문자에서 ‘0’의 아스키 코드값을 빼 문자를 숫자로 변환했다. 변환한 숫자를 sum에 더해 모든 자리수의 합을 구했다.

int get_integer_sum(string a, int a_length) {
	int sum = 0;

	for (int i = 0; i < a_length; i++)
		if (a[i] >= '0' && a[i] <= '9')
			sum += a[i] - '0';

	return sum;
}

코드

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

int get_integer_sum(string a, int a_length) {
	int sum = 0;

	for (int i = 0; i < a_length; i++)
		if (a[i] >= '0' && a[i] <= '9')
			sum += a[i] - '0';

	return sum;
}

int compare(string a, string b) {
	// a, b의 길이
	int a_length = a.length(), b_length = b.length();
	// a, b의 모든 자리수의 합
	int a_sum = get_integer_sum(a, a_length), b_sum = get_integer_sum(b, b_length);
	
	if (a_length != b_length)
		return a_length < b_length;
	else
		if (a_sum != b_sum)
			return a_sum < b_sum;
		else
			// 사전순으로 비교
			return a < b;
}

int main() {
	int n;
	cin >> n;

	// 시리얼 번호를 저장한 array
	string serial_numbers[n];

	for (int i = 0; i< n; i++)
		cin >> serial_numbers[i];

	sort(serial_numbers, serial_numbers + n, compare);

	for (int i = 0; i < n; i++)
		cout << serial_numbers[i] << "\n";

	return 0;
}

채점 결과