문제

BOJ 1431, 시리얼 번호

핵심

• 입력의 크기가 $50$이라 구현에 초점을 맞춘다.
• 비교 함수를 작성하는 법을 물어보는 문제이다. A와 B의 길이가 다르다면 짧은 것이 먼저 오고, 길이가 같다면 각 자릿수의 합을 비교해서 작은 합이 먼저 온다. 만약 둘 다 같다면 사전 순으로 비교한다.

개선

코드

시간복잡도

• $O(N\times logN)$

C++

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

int findSum(string& s) {
	int result = 0;
	for (auto& c : s) {
		if (c >= '0' && c <= '9')
			result += c - '0';
	}
	return result;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<string> v;
	for (int i = 0; i < n; ++i) {
		string num;
		cin >> num;
		v.push_back(num);	
	}
	sort(v.begin(), v.end(), [](auto &a, auto &b) {
			if (a.length() != b.length())
				return a.length() < b.length();
			int sumA = findSum(a);
			int sumB = findSum(b);
			if (sumA != sumB)
				return sumA < sumB;
			return a < b;
	});
	for (auto e : v)
		cout << e << '\n';
}

Java

import java.io.*;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        ArrayList<String> nums = new ArrayList<>(50);
        for (int i = 0; i < n; i++)
            nums.add(br.readLine());
        nums.sort((a, b) -> {
            if (a.length() != b.length())
                return Integer.compare(a.length(), b.length());
            int sumA = findSum(a);
            int sumB = findSum(b);
            if (sumA != sumB)
                return Integer.compare(sumA, sumB);
            return a.compareTo(b);
        });
        for (var e : nums)
            bw.write(e + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    private static int findSum(String str) {
        int ret = 0;
        for (var c : str.toCharArray()) {
            if (c >= '0' && c <= '9')
                ret += c - '0';
        }
        return ret;
    }
}