문제
알고리즘][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;
}채점 결과
0_0