[백준/BOJ] 1431번 - 시리얼 번호 (C++)

문제 링크

 

코딩하기 전 생각하기

/*
입력받은 문자열을 벡터에 저장한다.
sort 함수를 쓰기 전에 compare 함수를 만들자.
    두 문자열의 길이가 다르면, 더 길이가 짧은 문자열이 앞으로 가게 한다.
    두 문자열의 숫자인 자릿수의 합을 비교해서 작은 합을 가지는 문자열이 앞으로 가게 한다.
    숫자 자릿수의 합이 같으면, 문자열 자체를 비교해서 먼저 사전에 나오는 문자열이 앞으로 가게 한다.
compare 함수를 sort 함수의 인수로 넣고 벡터를 정렬한다.
벡터를 출력한다.
*/

 

---

 

코드

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

bool compare(string a, string b) {
    if ( a.length() != b.length() )
        return a.length() < b.length();
    int sum_a = 0, sum_b = 0;
    for ( auto c : a ) {
        if ( c >= '0' && c <= '9' ) sum_a += (c - '0');
    }
    for ( auto c : b ) {
        if ( c >= '0' && c <= '9' ) sum_b += (c - '0');
    }
    if ( sum_a != sum_b )
        return sum_a < sum_b;
    return a < b;
}

int main() {
    vector<string> v;
    string s;
    int n;
    cin >> n;
    for ( int i = 0; i < n; i++ ) {
        cin >> s;
        v.push_back(s);
    }
    sort(v.begin(), v.end(), compare);
    for ( int i = 0; i < n; i++ )
        cout << v[i] << '\n';
}

 

---

 

느낀점

 

데이터구조 수업에서 sorting을 할 때 배웠던 compare 함수를 곁들여 sort 함수를 사용하는 법을 응용할 수 있어서 좋았다.

한 번에 통과를 못 했는데 자릿수 합을 구할 때 (int)c 이런 식으로 잘못 형 변환을 했기 때문이었다. (아스키코드 숫자 합이었어도 결론적으로 틀리게 정렬하지는 않았을 텐데 어떤 TC에서 걸린 걸까)

이제 정렬문제는 자신있다!

라고 애송이가 말했다.

 

(주의) 기록용으로 작성한 글입니다. 코드가 허접하거나 알고리즘의 효율이 낮을 수 있습니다.

댓글 환영합니다!