売れた商品の番号を重複なしで数える

配列の処理
問題 06
やさしい
目安 11 分

1 日に売れた商品の番号の並びから、重複を除いた商品の数と、商品ごとの売れた個数を番号の小さい順に出す。並べ替えと数え上げを組み合わせる練習です。

本番の試験は PC で受けることが多いので、PC での練習をすすめます。スマホでも、読んで、書いて、採点するところまで動きます。

入力は標準入力から読み、答えは標準出力に書きます。1 テストあたり 3 秒までです。

問題

ある店のレジには、1 日に売れた商品の番号が、売れた順に N 個記録されています。同じ商品が何度売れることもあるので、同じ番号が何度も出てきます。

売れた商品が何種類あるかを K として、1 行目に K を出力してください。続く K 行に、売れた商品の番号と、その商品が売れた個数を、番号の小さい順に 1 行ずつ出力してください。

入力の形式

N
a_1 a_2 ... a_N

1 行目に記録の数 N、2 行目に売れた商品の番号 a_i が、売れた順に空白 1 つで区切られて並びます。

出力の形式

K + 1 行を出力します。1 行目に種類の数 K を書きます。2 行目からの K 行には、商品の番号とその売れた個数を、空白 1 つで区切って書きます。行は商品の番号の小さい順に並べます (番号は同じものが 2 行に出ないので、並びは 1 つに決まります)。

制約

N は、1 以上 200000 以下の整数です
a_i は、1 以上 1000000000 以下の整数です

入力と出力の例

例 1

番号 3 が 2 個、5 が 3 個、1 が 1 個売れています。種類は 3 つで、番号の小さい順に 1、3、5 と並べます。

入力

6
5 3 5 1 3 5

出力

例 2

同じ商品だけが売れた日は、種類が 1 つです。番号は数として比べるので、9 は 10 より前に来ます。

入力

4
10 9 10 10

出力

2
9 1
10 3

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

全部のテストに通ると、解答と考え方が開きます。

先にヒントを試すと、自分で解けた手応えが残ります。どうしても詰まったときは、ここから開けます。

解答

辞書で番号ごとの個数を数え、番号を数として小さい順に並べ替えて書き出します。数えるのが O(N)、並べ替えが O(K log K) です。並べ替えてから同じ番号が続く長さを数える書き方でも、同じ速さで解けます。

Python

import sys

data = sys.stdin.read().split()
n = int(data[0])
items = list(map(int, data[1:1 + n]))

counts = {}
for item in items:
    counts[item] = counts.get(item, 0) + 1

lines = [str(len(counts))]
for item in sorted(counts):
    lines.append(f"{item} {counts[item]}")
print("\n".join(lines))

JavaScript

const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const items = data.slice(1, 1 + n);

const counts = new Map();
for (const item of items) {
  counts.set(item, (counts.get(item) ?? 0) + 1);
}

const keys = [...counts.keys()].sort((x, y) => x - y);
const lines = [String(keys.length)];
for (const key of keys) lines.push(`${key} ${counts.get(key)}`);
console.log(lines.join("\n"));

計算量

時間は O(N + K log K) で、K は種類の数 (最大で N) です。

遅い解き方は、重複なしの並びを先頭から探して「まだ無い番号か」を確かめ、そのあと種類ごとに全部の記録を数え直す書き方です。どちらも O(N × K) で、ほとんどの番号が違う 20 万個の入力では数百億回の比べになり、どの言語でも時間切れになります。Python の x not in uniq や JavaScript の includes と filter は 1 行で書けますが、中では先頭から全部を見ています。

よくある間違い

JavaScript で sort() に比べる関数を渡さず、番号が文字の順 (1、10、9) に並ぶ
1 行目の種類の数 K を書き忘れる、または記録の数 N を書いてしまう
種類ごとの個数を、重複なしの並びを作ったあとで count や filter で数え直し、そこで O(N × K) かかる
番号を数に直さず文字のまま並べ替えて、例 2 のように 9 と 10 の順が逆になる

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026/10/31

main.py

import sys

data = sys.stdin.read().split()
n = int(data[0])
items = list(map(int, data[1:1 + n]))

# ここから書く

入力

6
5 3 5 1 3 5

出力

「実行する」を押すと、ここに出力が出ます

できているか「提出して採点」を押すと、隠れたテストを全部走らせて、通ったかをここに出します