文字列の比較文字コード条件つき並べ替えP0142

ファイル名の自然順ソート

一行目にファイル名の数 n が与えられ、続いてファイル名が一行に一つずつ n 個与えられる。
ファイル名を人が読む順（自然順）に並べ替え、一行に一つずつ出力せよ。
二つの名前 a、b の順は、二つの名前を先頭から次のように順に比べて決める。
数のかたまりの長さが違うことがあるので、二つの名前で今比べている位置は違うことがある。
二つの名前の今の文字がどちらも数字（0〜9）なら、それぞれその位置から続く数字を最後までまとめて一つの数のかたまりとみなす。
二つの数のかたまりは先頭の 0 を除いた数の大きさで比べ、小さいほうが前である（"9" < "10"、"007" と "7" は同じ）。
数が同じなら、それぞれ自分の数のかたまりのすぐ後ろの文字から比較を続ける。
二文字のうち一つでも数字でなければ、二文字のコード（ASCII）を比べて小さいほうが前であり、同じなら両方とも次の文字に進む。
文字コードは - が 45、.
が 46、数字 0〜9 が 48〜57、英大文字が 65〜90、_ が 95、英小文字が 97〜122 である。
片方の名前だけが先に終わったら、先に終わったほうが前である。
二つの名前が同時に終わるまで違いがなければ（"a01" と "a1" のように先頭の 0 だけが違うなら）、二つの名前全体を先頭の文字から一文字ずつ文字コードで比べ、最初に違う文字のコードが小さいほうが前である。
このときも片方が先に終わればそちらが前である（"a0" は "a00" より前）。
数のかたまりは 30 桁まで長くなることがある。

入力: 1 ≤ n ≤ 1000。
名前は 1〜30 文字で、英大文字・小文字、数字、- .
_ だけからなる。
同じ名前が何度か出ることがある
出力: 並べ替えた名前 n 行

例 1 · stdin

8
file10.txt
file9.txt
file1.txt
img_002.png
img_2.png
img_10.png
File2.txt
file1-old.txt

stdout

File2.txt
file1-old.txt
file1.txt
file9.txt
file10.txt
img_002.png
img_2.png
img_10.png

例 2 · stdin

5
v1.10
v1.9
v1.9.1
v1.09
v1.1

stdout

v1.1
v1.09
v1.9
v1.9.1
v1.10

main.py プログラミング言語実行バージョン

入力(stdin)

実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。

$ 準備完了

コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。

ほかの言語では？言語別の解答を見る · 8 言語の解答

落とし穴は四つです。
一つ目、そのまま並べ替えると文字コード順なので "file10" が "file9" より前になります（1 が 9 より小さいからです）。
比較関数を自分で渡す必要があります：Python sorted(key=cmp_to_key(f))、JS・TS sort(f)、Java list.sort(Main::f)、C# List.Sort(f)、C qsort、C++ std::sort に f(a, b) < 0、Craykon names.並べ替え(f)（負・0・正を返す関数）。
二つ目、数のかたまりを数に変えるとあふれます。
30 桁は C strtoll・C++ stoll・Java Long.parseLong・C# long.Parse が扱う 19 桁を超えます。
strtoll は LLONG_MAX で止まって違う数が同じになり、stoll・parseLong・long.Parse は例外を投げます。
JS・TS Number() と Craykon 数に() は 2^53 を超えると精度を失い、やはり違う数が同じになります。
Python int はあふれません。
先頭の 0 を除いて桁数を先に、同じなら文字列を比べれば、どの言語でもあふれません。
三つ目、先頭の 0 を除かずに桁数を比べると "007" が "10" より大きくなります。
四つ目、最後まで同じとき 0 を返すと、"a1" と "a01" の順が入力順で変わります。
最後に全体を文字コードで比べれば完全に同じ名前だけが同じになるので、C qsort・C++ std::sort・C# List.Sort のように安定ソートでなくても答えが一つに決まります。
文字コードの比較は Python ord(c)、JS・TS charCodeAt、Java・C#・C・C++ は char の引き算、Craykon 文字.コード(c) です。
文字列全体の比較は C# では string.CompareOrdinal を使います。
string.Compare は文化圏の規則なので大文字小文字や記号の順が違います。

Pythonmain.py · 42 行

import sysfrom functools import cmp_to_key  def is_digit(c):    return "0" <= c <= "9"  def digit_end(s, i):    while i < len(s) and is_digit(s[i]):        i += 1    return i  def 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;}