import sysfrom functools import cmp_to_keydef is_digit(c): return "0" <= c <= "9"def digit_end(s, i): while i < len(s) and is_digit(s[i]): i += 1 return idef compare_natural(a, b): i = j = 0 while i < len(a) and j < len(b): if is_digit(a[i]) and is_digit(b[j]): ie, je = digit_end(a, i), digit_end(b, j) # 앞의 0을 떼면 자릿수가 많은 쪽이 큰 수다(수로 바꾸지 않아 넘치지 않는다) x, y = a[i:ie].lstrip("0"), b[j:je].lstrip("0") if len(x) != len(y): return len(x) - len(y) if x != y: return -1 if x < y else 1 i, j = ie, je else: if a[i] != b[j]: return ord(a[i]) - ord(b[j]) i += 1 j += 1 if i < len(a): return 1 # b가 먼저 끝났다 if j < len(b): return -1 # a가 먼저 끝났다 return -1 if a < b else (1 if a > b else 0) # "a01"과 "a1": 글자 코드 순data = sys.stdin.read().split("\n")n = int(data[0])names = data[1:1 + n]print("\n".join(sorted(names, key=cmp_to_key(compare_natural))))
JavaScriptmain.js · 32 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const names = lines.slice(1, 1 + n);const isDigit = (c) => c >= "0" && c <= "9";function compareNatural(a, b) { let i = 0, j = 0; while (i < a.length && j < b.length) { if (isDigit(a[i]) && isDigit(b[j])) { let ie = i, je = j; while (ie < a.length && isDigit(a[ie])) ie++; while (je < b.length && isDigit(b[je])) je++; // Number()로 바꾸면 2^53을 넘는 수에서 정밀도를 잃는다 — 문자열 그대로 비교 const x = a.slice(i, ie).replace(/^0+/, ""); const y = b.slice(j, je).replace(/^0+/, ""); if (x.length !== y.length) return x.length - y.length; if (x !== y) return x < y ? -1 : 1; i = ie; j = je; } else { if (a[i] !== b[j]) return a.charCodeAt(i) - b.charCodeAt(j); i++; j++; } } if (i < a.length) return 1; if (j < b.length) return -1; return a < b ? -1 : a > b ? 1 : 0; // < 는 글자 코드 순(localeCompare 아님)}console.log(names.sort(compareNatural).join("\n"));
TypeScriptmain.ts · 33 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n: number = Number(lines[0]);const names: string[] = lines.slice(1, 1 + n);const isDigit = (c: string): boolean => c >= "0" && c <= "9";function compareNatural(a: string, b: string): number { let i = 0, j = 0; while (i < a.length && j < b.length) { if (isDigit(a[i]) && isDigit(b[j])) { let ie = i, je = j; while (ie < a.length && isDigit(a[ie])) ie++; while (je < b.length && isDigit(b[je])) je++; // Number()로 바꾸면 2^53을 넘는 수에서 정밀도를 잃는다 — 문자열 그대로 비교 const x: string = a.slice(i, ie).replace(/^0+/, ""); const y: string = b.slice(j, je).replace(/^0+/, ""); if (x.length !== y.length) return x.length - y.length; if (x !== y) return x < y ? -1 : 1; i = ie; j = je; } else { if (a[i] !== b[j]) return a.charCodeAt(i) - b.charCodeAt(j); i++; j++; } } if (i < a.length) return 1; if (j < b.length) return -1; return a < b ? -1 : a > b ? 1 : 0; // < 는 글자 코드 순(localeCompare 아님)}console.log(names.sort(compareNatural).join("\n"));
JavaMain.java · 52 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;public class Main { static boolean isDigit(char c) { return c >= '0' && c <= '9'; } static String stripZeros(String s) { int k = 0; while (k < s.length() && s.charAt(k) == '0') k++; return s.substring(k); } static int compareNatural(String a, String b) { int i = 0, j = 0; while (i < a.length() && j < b.length()) { char p = a.charAt(i), q = b.charAt(j); if (isDigit(p) && isDigit(q)) { int ie = i, je = j; while (ie < a.length() && isDigit(a.charAt(ie))) ie++; while (je < b.length() && isDigit(b.charAt(je))) je++; // Long.parseLong은 19자리를 넘으면 예외 — 문자열 그대로 비교 String x = stripZeros(a.substring(i, ie)), y = stripZeros(b.substring(j, je)); if (x.length() != y.length()) return x.length() - y.length(); int c = x.compareTo(y); if (c != 0) return c; i = ie; j = je; } else { if (p != q) return p - q; i++; j++; } } if (i < a.length()) return 1; if (j < b.length()) return -1; return a.compareTo(b); // String.compareTo는 글자 코드 순 } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); List<String> names = new ArrayList<>(); for (int k = 0; k < n; k++) names.add(in.readLine()); names.sort(Main::compareNatural); System.out.println(String.join("\n", names)); }}
C#Main.cs · 47 行
using System;using System.Collections.Generic;class Program{ static bool IsDigit(char c) => c >= '0' && c <= '9'; static int CompareNatural(string a, string b) { int i = 0, j = 0; while (i < a.Length && j < b.Length) { if (IsDigit(a[i]) && IsDigit(b[j])) { int ie = i, je = j; while (ie < a.Length && IsDigit(a[ie])) ie++; while (je < b.Length && IsDigit(b[je])) je++; // long.Parse는 19자리를 넘으면 OverflowException — 문자열 그대로 비교 string x = a.Substring(i, ie - i).TrimStart('0'); string y = b.Substring(j, je - j).TrimStart('0'); if (x.Length != y.Length) return x.Length - y.Length; int c = string.CompareOrdinal(x, y); if (c != 0) return c; i = ie; j = je; } else { if (a[i] != b[j]) return a[i] - b[j]; i++; j++; } } if (i < a.Length) return 1; if (j < b.Length) return -1; return string.CompareOrdinal(a, b); // string.Compare(a, b)는 문화권 규칙이라 다르다 } static void Main() { int n = int.Parse(Console.ReadLine()); var names = new List<string>(); for (int k = 0; k < n; k++) names.Add(Console.ReadLine()); names.Sort(CompareNatural); // 끝까지 같으면 완전히 같은 문자열이라 안정 정렬이 아니어도 된다 Console.WriteLine(string.Join("\n", names)); }}
C++main.cpp · 44 行
#include <algorithm>#include <iostream>#include <string>#include <vector>bool isDigit(char c) { return c >= '0' && c <= '9'; }int compareNatural(const std::string& a, const std::string& b) { size_t i = 0, j = 0; while (i < a.size() && j < b.size()) { if (isDigit(a[i]) && isDigit(b[j])) { size_t ie = i, je = j; while (ie < a.size() && isDigit(a[ie])) ie++; while (je < b.size() && isDigit(b[je])) je++; // std::stoll은 19자리를 넘으면 out_of_range — 문자열 그대로 비교 while (i < ie && a[i] == '0') i++; while (j < je && b[j] == '0') j++; std::string x = a.substr(i, ie - i), y = b.substr(j, je - j); if (x.size() != y.size()) return x.size() < y.size() ? -1 : 1; if (x != y) return x < y ? -1 : 1; i = ie; j = je; } else { if (a[i] != b[j]) return (unsigned char)a[i] - (unsigned char)b[j]; i++; j++; } } if (i < a.size()) return 1; if (j < b.size()) return -1; return a.compare(b);}int main() { int n; std::string line; std::getline(std::cin, line); n = std::stoi(line); std::vector<std::string> names(n); for (auto& s : names) std::getline(std::cin, s); std::sort(names.begin(), names.end(), [](const std::string& a, const std::string& b) { return compareNatural(a, b) < 0; }); for (const auto& s : names) std::cout << s << '\n';}
Cmain.c · 52 行
#include <stdio.h>#include <stdlib.h>#include <string.h>static char names[1000][40];static int isDigit(char c) { return c >= '0' && c <= '9'; }static int compareNatural(const char *a, const char *b) { int i = 0, j = 0; while (a[i] && b[j]) { if (isDigit(a[i]) && isDigit(b[j])) { int ie = i, je = j; while (isDigit(a[ie])) ie++; while (isDigit(b[je])) je++; /* 앞의 0을 건너뛴다. strtoll은 19자리를 넘으면 넘쳐서 쓰지 않는다 */ while (i < ie && a[i] == '0') i++; while (j < je && b[j] == '0') j++; int lx = ie - i, ly = je - j; if (lx != ly) return lx - ly; int c = strncmp(a + i, b + j, lx); if (c != 0) return c; i = ie; j = je; } else { if (a[i] != b[j]) return (unsigned char)a[i] - (unsigned char)b[j]; i++; j++; } } if (a[i]) return 1; if (b[j]) return -1; return strcmp(a, b); /* strcmp는 글자 코드 순 */}static int cmp(const void *p, const void *q) { return compareNatural((const char *)p, (const char *)q);}int main(void) { int n; char line[64]; if (!fgets(line, sizeof line, stdin)) return 0; sscanf(line, "%d", &n); for (int k = 0; k < n; k++) { if (!fgets(names[k], sizeof names[k], stdin)) break; names[k][strcspn(names[k], "\n")] = '\0'; } qsort(names, n, sizeof names[0], cmp); for (int k = 0; k < n; k++) puts(names[k]); return 0;}
Craykonmain.cray · 94 行
n = 控制台.读行().转数字();names = [];循环 (k = 0; k < n; k++){ names.添加(控制台.读行());}names.排序(compareNatural);遍历 (s 在 names){ 控制台.输出(s);}// 숫자 글자인지: 글자 코드 48("0") ~ 57("9")isDigit(ch){ c = 字符.编码(ch); 返回 c >= 48 && c <= 57;}// 숫자 덩이에서 앞의 0을 뗀다stripZeros(s){ k = 0; 当 (k < s.长度 && s[k] == "0") { k += 1; } 返回 s.截取(k);}compareNatural(a, b){ i = 0; j = 0; 当 (i < a.长度 && j < b.长度) { 如果 (isDigit(a[i]) && isDigit(b[j])) { ie = i; je = j; 当 (ie < a.长度 && isDigit(a[ie])) { ie += 1; } 当 (je < b.长度 && isDigit(b[je])) { je += 1; } // 수로변환은 2^53을 넘으면 정밀도를 잃는다 — 문자열 그대로 비교 x = stripZeros(a.截取(i, ie - i)); y = stripZeros(b.截取(j, je - j)); 如果 (x.长度 != y.长度) { 返回 x.长度 - y.长度; } 如果 (x != y) { 如果 (x < y) { 返回 -1; } 返回 1; } i = ie; j = je; } 否则 { 如果 (a[i] != b[j]) { 返回 字符.编码(a[i]) - 字符.编码(b[j]); } i += 1; j += 1; } } 如果 (i < a.长度) { 返回 1; } 如果 (j < b.长度) { 返回 -1; } 如果 (a < b) { 返回 -1; } 如果 (a > b) { 返回 1; } 返回 0;}