첫 줄에 파일 이름 수 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글자이고 영어 대문자·소문자, 숫자, - . _ 로만 이루어진다. 같은 이름이 여러 번 나올 수 있다
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 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, 크레이콘 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()와 크레이콘 수로변환()은 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 빼기, 크레이콘 글자.코드(c)예요. 문자열 전체 비교는 C# string.CompareOrdinal을 써야 해요. string.Compare는 문화권 규칙이라 대소문자와 기호 순서가 달라요.
Pythonmain.py · 42 줄
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;}