[BOJ / C++] 시리얼 번호 (정렬)

문제링크: https://www.acmicpc.net/problem/1431

 

1. 코드

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;
    
    vector<string> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    sort(arr.begin(), arr.end(), [](const string& a, const string& b){
        if (a.length() != b.length()) return a.length() < b.length();
        
        int aNum = 0, bNum = 0;
        for (char c: a) {
            if (isdigit(c)) aNum += c - '0';
        }
        for (char c: b) {
            if (isdigit(c)) bNum += c - '0';
        }
        
        if (aNum != bNum) return aNum < bNum;
        else return a < b;
    });

    for (int i = 0; i < n; i++) {
        cout << arr[i] << '\n';
    }
}

 

 

2. 분석

sort의 비교함수를 람다함수로 작성해주면 된다. cctype 헤더에 있는 문자 분류, 문자 변환 함수를 정리하면 다음과 같다.

 

• std::isalpha(int ch) : 알파벳(A–Z, a–z)이면 참
• std::isdigit(int ch) : 숫자(0–9)이면 참
• std::islower(int ch) : 소문자(a–z)이면 참
• std::isupper(int ch) : 대문자(A–Z)이면 참

 

 

• std::toupper(int ch) : 소문자를 대응하는 대문자로 변환
• std::tolower(int ch) : 대문자를 대응하는 소문자로 변환

비교함수를 작성할 때 주의할 사항은 다음과 같다.

 

1. 비교함수는 두 값이 같을 때 (또는 우선순위가 같을 때) false를 반환

// 틀린 방법 (런타임에러 발생가능)
bool cmp(int a, int b) {
	if (a >= b) return true;
    return false;
}

// 올바른 방법
bool cmp(int a, int b) {
	return a > b;   // 값이 같을 때 false를 리턴해야한다!
}

 

 

2. 비교함수의 인자로 객체 전달 시 reference 사용

// & 미사용으로 인한 복사 오버헤드 발생
bool cmp(string a, string b) {
	return a.back() < b.back();
}

// 올바른 const, reference 사용
bool cmp(const string& a, const string& b) {
	return a.back() < b.back();
}

 

 

 

3. 시간복잡도

sort 함수는 O(nlogn)을 보장한다. 따라서 시간복잡도는 O(nlogn)이고, 시간제한 2초에 n<=50 이므로 통과 가능하다.