백준/1431/sort/시리얼 번호
STL_sort 연습겸 문제를 풀어봤는데 어려웠다.
sort(시작점,끝점,sort의 기준이되는 함수)를 사용하는 문제인데
- A와 B의 길이가 다르면, 짧은 것이 먼저 온다.
- 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)
- 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.
해당 조건을 차례대로 만족해야 한다. 처음에는 흔히 sort를 사용하면 나오는
invalid comparator runtime error에 많이 막혔다.
bool func(const string &a, const string &b)
a와b를 비교햇을때 a<b가 true가 나왔을 경우 a>b 그리고 a==b는 false가 나오게끔해야 invalid comparator runtime error가 안나오는데 그 조건을 맞추기가 쉽지 않았다.
그래서 처음에는 각각의 조건을 함수로 만들어 sort를 총 3번 햇는데
이럴 경우 1번식과 2번식은 상관없지만 3번식에 경우에 반례가 생긴다.
input
2
A132
Z111
output
A132
Z111
answer
Z111
AZ32
위와 같은 반례가 생기는 이유는 조건의 우선순위를 무시했기 때문이다.
즉, 한 함수안에서 모든 조건을 받아들여한다.
그래서 두번째 풀이는 한 함수안에 모든 조건을 다 집어넣었는데
input
2
A3
11
output
A3
11
answer
11
A3
위와같은 반례가 생겼다. 반례가 생기는 조건을 확인하기 위해 우선 해당 배열을 비교하는 부분을
cout을 통해 찾았더니
if (count_a < count_b) return true;
이 부분을 들어가지 않고 있었습니다. 즉, 2번째 조건부에 문제라 생각해
count_a와 count_b를 비교해보니 ASCII값 그대로 더해지고 있엇습니다.
int()가 문자 자체를 int로 바꿔준다 생각했는데 착오였습니다.
애초에 char형은 문자를 나타내기 위한 int형인것을 생각하지 못하고 있었습니다.
그래서 시작점이 되는 '0'을 빼주니 값이 정상적으로 출력되었습니다.
풀이
1. 첫번째 풀이
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<string>V;
bool func(const string &a, const string &b) {
if (a.length() < b.length())return true;
return false;
}
bool func1(const string&a, const string &b) {
int count_a = 0;
int count_b = 0;
if (a.length() == b.length()) {
for (int i = 0; a[i] != '\0'; i++) {
if (a[i] >= '0' && a[i] <= '9') {
count_a += int(a[i]);
}
}
for (int i = 0; b[i] != '\0'; i++) {
if (b[i] >= '0' && b[i] <= '9') {
count_b += int(b[i]);
}
}
if (count_a < count_b)
return true;
return false;
}
return false;
}
bool func2(const string &a, const string &b) {
if (a.length() == b.length()) {
if (a < b)return true;
return false;
}
return false;
}
int main(void) {
ios::sync_with_stdio(0);
cout.tie(0); cin.tie(0);
cin >> N;
string tmp;
for (int i = 0; i < N; i++) {
cin >> tmp;
V.push_back(tmp);
}
sort(V.begin(), V.end(), func);
sort(V.begin(), V.end(), func1);
sort(V.begin(), V.end(), func2);
for (auto x : V)
cout << x << '\n';
}2. 두번째 풀이
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<string>V;
bool func(const string &a, const string &b) {
int count_a = 0;
int count_b = 0;
if (a.length() < b.length())return true;
if (a.length() == b.length()) {
for (int i = 0; a[i] != '\0'; i++) {
if (a[i] >= '0' && a[i] <= '9') {
count_a += int(a[i]);
}
}
for (int i = 0; b[i] != '\0'; i++) {
if (b[i] >= '0' && b[i] <= '9') {
count_b += int(b[i]);
}
}
//cout<<count_a<<","<<count_b<<'\n';
if (count_a < count_b){
//cout << "in" << '\n';
return true;
}
if (count_a == count_b) {
if (a < b)
return true;
return false;
}
}
return false;
}
int main(void) {
ios::sync_with_stdio(0);
cout.tie(0); cin.tie(0);
cin >> N;
string tmp;
for (int i = 0; i < N; i++) {
cin >> tmp;
V.push_back(tmp);
}
sort(V.begin(), V.end(), func);
for (auto x : V)
cout << x << '\n';
}3. 세번째 풀이
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int N;
vector<string>V;
bool func(const string &a, const string &b) {
int count_a = 0;
int count_b = 0;
if (a.length() < b.length())return true;
if (a.length() == b.length()) {
for (int i = 0; a[i] != '\0'; i++) {
if (a[i] >= '0' && a[i] <= '9') {
count_a += a[i]-'0';
}
}
for (int i = 0; b[i] != '\0'; i++) {
if (b[i] >= '0' && b[i] <= '9') {
count_b += b[i]-'0';
}
}
if (count_a < count_b)
return true;
if (count_a == count_b) {
if (a < b)
return true;
return false;
}
}
return false;
}
int main(void) {
ios::sync_with_stdio(0);
cout.tie(0); cin.tie(0);
cin >> N;
string tmp;
for (int i = 0; i < N; i++) {
cin >> tmp;
V.push_back(tmp);
}
sort(V.begin(), V.end(), func);
for (auto x : V)
cout << x << '\n';
}