{ }codelper
リストの並べ替えP0320

数の大きさの順と辞書順

整数 n 個を二通りの順に並べる。
一つ目は数の大きさの順で、小さい数から順に並べる。
二つ目は辞書順で、数を入力に書かれたとおりの文字列として比べる。
二つの文字列は前から一文字ずつ比べ、最初に異なる文字がより前にあるほうが先で、文字の順番は -、0、1、…、9 である。
一方の文字列がもう一方の先頭部分とまったく同じなら、短いほうが先である。
一行目に n が、二行目に整数 n 個が空白一つで区切って与えられる。
一行目に数の大きさの順で、二行目に辞書順で、n 個を空白一つで区切って出力せよ。
同じ数は出てきた回数だけすべて出力する。
三行目には、二つの行で同じ位置に同じ数が置かれている位置の個数を出力せよ。

入力
1 ≤ n ≤ 1,000。
整数は -2,000,000,000 以上 2,000,000,000 以下で、カンマなしの数字だけで与えられる。
負の数は先頭に - が付き、+ 記号や不要な 0(007、-0)は付かない
出力
三行:数の大きさの順、辞書順、同じ位置に同じ数が置かれている位置の個数
例 1 · stdin
6
10 9 -3 100 -20 9
stdout
-20 -3 9 9 10 100
-20 -3 10 100 9 9
2
例 2 · stdin
2
2000000000 -2000000000
stdout
-2000000000 2000000000
-2000000000 2000000000
2
main.py
入力(stdin)

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

$ 準備完了

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

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

同じ並べ替えの道具でも、何が入っているかで順番の決め方が変わります。
Python sorted(tokens, key=int) は数に変えた値で、sorted(tokens) は文字列のまま比べます。
Java Arrays.sort は int[] なら数の大きさ、String[] なら辞書順で、C++ std::sort も vector<int> と vector<string> で同じように変わります。
Craykon リスト.並べ替え() も、数のリストは数の大きさ、文字列のリストは辞書順です。
C qsort は比べる関数を必ず渡すので、数には (x > y) - (x < y)、文字列には strcmp を使います。
C# は Array.Sort(byNum) と Array.Sort(byText, StringComparer.Ordinal) で、文字列は文字コードで比べるように伝えます(既定の比較はカルチャの規則に従います。
- と数字だけのこの問題では採点環境で二つの結果は同じですが、文字コード順にしたいと明示しておくほうが安全です)。
JS・TS だけが逆です:何も渡さない sort() が辞書順で、数の大きさの順は sort((x, y) => x - y) と比べる関数を渡す必要があります。
落とし穴は四つ:① 数に変えなかったり比べ方を伝えなかったりすると、一行目が辞書順になります(例 1 の一行目が -20 -3 10 100 9 9 に)。
JS nums.sort() は数の配列でも文字列に変えて比べ、Python で key=int を忘れたり、Craykon で 数に なしに文字列のリストを 並べ替え() したりしても同じです。
② その場での並べ替えはコピーを作りません。
JS sort はその配列を並べ替えてそのまま返すので、const byNum = nums.sort(...) と const byText = nums.sort() は同じ一つの配列です。
Python by_num = tokens もコピーではありません。
二つの行が同じになり、三行目が n になります(例 1 が 6 に)。
JS [...tokens]、Python sorted、Java clone()、Craykon 部分リスト(0, n) で別々に作ります。
③ Python by_num = tokens.sort(key=int) は並べ替えたリストではなく None を入れるので、それを使う行で TypeError で止まります。
④ 比べる関数を引き算で書く C return x - y; と Java (x, y) -> x - y は、2000000000 - (-2000000000) が int の範囲をあふれて負になり、大きい数が前に置かれます(例 2 の一行目が 2000000000 -2000000000 に)。
C は (x > y) - (x < y)、Java は Integer.compare(x, y) を使います。
JS の x - y は数が浮動小数点なので、この範囲ではあふれません。

Pythonmain.py · 12 行
n = int(input())tokens = input().split() # sorted는 새 목록을 돌려주고 원래 목록은 그대로 둔다by_num = sorted(tokens, key=int)  # 수로 바꾼 값을 기준으로: 수 크기 순서by_text = sorted(tokens)          # 문자열 그대로: 사전 순서 same = sum(1 for x, y in zip(by_num, by_text) if x == y) print(*by_num)print(*by_text)print(same)
JavaScriptmain.js · 18 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const tokens = lines[1].trim().split(/\s+/); // sort는 그 배열 자체를 정렬하므로, 순서마다 배열을 따로 만든다// 수 크기 순서는 견주는 함수를 꼭 넘겨야 한다const byNum = tokens.map(Number).sort((x, y) => x - y);// 아무것도 넘기지 않은 sort()는 문자열로 견준다: 사전 순서const byText = [...tokens].sort(); let same = 0;for (let i = 0; i < n; i++) {  if (byNum[i] === Number(byText[i])) same++;} console.log(byNum.join(" "));console.log(byText.join(" "));console.log(same);
TypeScriptmain.ts · 19 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n: number = Number(lines[0]);const tokens: string[] = lines[1].trim().split(/\s+/); // sort는 그 배열 자체를 정렬하므로, 순서마다 배열을 따로 만든다// 수 크기 순서는 견주는 함수를 꼭 넘겨야 한다const byNum: number[] = tokens.map(Number).sort((x: number, y: number) => x - y);// 아무것도 넘기지 않은 sort()는 문자열로 견준다: 사전 순서const byText: string[] = [...tokens].sort(); let same: number = 0;for (let i = 0; i < n; i++) {  if (byNum[i] === Number(byText[i])) same++;} console.log(byNum.join(" "));console.log(byText.join(" "));console.log(same);
JavaMain.java · 37 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays; public class Main {    public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        int n = Integer.parseInt(in.readLine().trim());        String[] tokens = in.readLine().trim().split(" +");         // int 배열을 정렬하면 수 크기 순서        int[] byNum = new int[n];        for (int i = 0; i < n; i++) byNum[i] = Integer.parseInt(tokens[i]);        Arrays.sort(byNum);         // String 배열을 정렬하면 사전 순서. clone으로 복사본을 만들어 정렬한다        String[] byText = tokens.clone();        Arrays.sort(byText);         int same = 0;        StringBuilder numLine = new StringBuilder();        StringBuilder textLine = new StringBuilder();        for (int i = 0; i < n; i++) {            if (byNum[i] == Integer.parseInt(byText[i])) same++;            if (i > 0) {                numLine.append(' ');                textLine.append(' ');            }            numLine.append(byNum[i]);            textLine.append(byText[i]);        }        System.out.println(numLine);        System.out.println(textLine);        System.out.println(same);    }}
C#Main.cs · 28 行
using System; class Program{    static void Main()    {        int n = int.Parse(Console.ReadLine().Trim());        string[] tokens = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);         // int 배열을 정렬하면 수 크기 순서        int[] byNum = Array.ConvertAll(tokens, int.Parse);        Array.Sort(byNum);         // 문자열은 StringComparer.Ordinal을 넘겨 글자 코드 순서(사전 순서)로 정렬한다        string[] byText = (string[])tokens.Clone();        Array.Sort(byText, StringComparer.Ordinal);         int same = 0;        for (int i = 0; i < n; i++)        {            if (byNum[i] == int.Parse(byText[i])) same++;        }         Console.WriteLine(string.Join(" ", byNum));        Console.WriteLine(string.Join(" ", byText));        Console.WriteLine(same);    }}
C++main.cpp · 28 行
#include <algorithm>#include <iostream>#include <string>#include <vector> int main() {    int n;    std::cin >> n;    std::vector<std::string> byText(n);    std::vector<int> byNum(n);    for (int i = 0; i < n; i++) {        std::cin >> byText[i];        byNum[i] = std::stoi(byText[i]);    }     // 같은 std::sort지만 int는 수 크기로, std::string은 사전 순서로 견준다    std::sort(byNum.begin(), byNum.end());    std::sort(byText.begin(), byText.end());     int same = 0;    for (int i = 0; i < n; i++) {        if (byNum[i] == std::stoi(byText[i])) same++;    }     for (int i = 0; i < n; i++) std::cout << byNum[i] << (i + 1 < n ? ' ' : '\n');    for (int i = 0; i < n; i++) std::cout << byText[i] << (i + 1 < n ? ' ' : '\n');    std::cout << same << '\n';}
Cmain.c · 39 行
#include <stdio.h>#include <stdlib.h>#include <string.h> /* 수 크기로 견준다. 빼기(x - y)는 int 범위를 넘칠 수 있어서 쓰지 않는다 */static int by_num(const void *a, const void *b) {    int x = *(const int *)a, y = *(const int *)b;    return (x > y) - (x < y);} /* 문자열로 견준다. strcmp가 바로 사전 순서다 */static int by_text(const void *a, const void *b) {    return strcmp((const char *)a, (const char *)b);} int main(void) {    int n;    static int nums[1000];    static char texts[1000][12]; /* "-2000000000"은 11글자, 끝 표시까지 12칸 */    scanf("%d", &n);    for (int i = 0; i < n; i++) {        scanf("%11s", texts[i]);        nums[i] = atoi(texts[i]);    }     /* qsort는 견주는 함수를 받는다. 배열마다 다른 함수를 넘긴다 */    qsort(nums, n, sizeof nums[0], by_num);    qsort(texts, n, sizeof texts[0], by_text);     int same = 0;    for (int i = 0; i < n; i++) {        if (nums[i] == atoi(texts[i])) same++;    }     for (int i = 0; i < n; i++) printf("%d%c", nums[i], i + 1 < n ? ' ' : '\n');    for (int i = 0; i < n; i++) printf("%s%c", texts[i], i + 1 < n ? ' ' : '\n');    printf("%d\n", same);    return 0;}
Craykonmain.cray · 27 行
n = コンソール.行読み().数に();tokens = コンソール.行読み().空白除去().分ける(); // 정렬()은 그 목록 자체를 정렬한다. 수 목록은 수 크기 순서가 된다byNum = [];それぞれ (t の中 tokens){    byNum.追加(t.数に());}byNum.並べ替え(); // 문자열 목록은 사전 순서가 된다. 부분목록으로 복사본을 만들어 정렬한다byText = tokens.部分リスト(0, n);byText.並べ替え(); same = 0;繰り返す (i = 0; i < n; i++){    もし (byNum[i] == byText[i].数に())    {        same++;    }} コンソール.書く(byNum.つなぐ(" "));コンソール.書く(byText.つなぐ(" "));コンソール.書く(same);