You are building the index at the back of a book.
You are given n records, each a word and the number of a page where the word appears.
The same word can appear on several lines, and a line with the same word and the same page number can appear more than once.
For every word print one line made of the word, a colon (:), one space, and the page list, in that order.
Print the words in alphabetical dictionary order (when one word is the beginning of another, the shorter word comes first).
Build the page list as follows.
Keep each page number of a word only once, and put the page numbers in increasing order.
Split the ordered page numbers into runs from the front. A page number that is exactly 1 more than the one before it belongs to the same run as that one; any other page number starts a new run.
Shorten a run of three or more page numbers to "first page-last page" (5, 6, 7 becomes 5-7, and 5, 6, 7, 8 becomes 5-8).
Do not shorten a run of two page numbers; write the two separately (5, 6 stays 5 and 6). A run of one page number is written as that number.
Put a comma and one space (", ") between the entries made this way.
Do not put a comma or a space at the end of the line.
Input
The first line gives n. Each of the next n lines gives a word and a page number separated by one space. 1 ≤ n ≤ 5,000, each word is a string of 1 to 10 lowercase English letters, 1 ≤ page number ≤ 100,000
Output
One line for each distinct word, in the form "word: page list". Page numbers are written as plain digits without commas (100000)
Example 1 · stdin
9
tree 12
stack 5
tree 3
stack 6
tree 5
tree 6
stack 5
tree 7
tree 13
stdout
stack: 5, 6
tree: 3, 5-7, 12, 13
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Putting a separator only 'between' the entries is what join does. It is one line in Python ", ".join(parts), JS and TS parts.join(", "), Java String.join(", ", parts), C# string.Join(", ", parts) and Craykon parts.Join(", "). C has no join and neither does C++ std::string, so you join by hand: 'print a comma first unless this is the first entry'. If you add ", " after every entry, a comma is left at the end of the line. What join accepts also differs: Python takes strings only, so a number in the list is a TypeError, and Java String.join also takes only a list of strings (List<Integer> is a compile error). JS, TS, C# and Craykon turn numbers into strings for you. Grouping is done with a map: Python dict + set, JS and TS Map + Set, Java TreeMap + TreeSet, C# SortedDictionary + SortedSet, C++ map + set (these three stay sorted as you insert), and in Craykon a Dict() holding lists. C has no map, so sort the (word, page) pairs with qsort to bring the same word together. Trap one: without a compare function, sort() in JS and TS turns even numbers into strings to compare them, so 9, 10, 100 becomes 10, 100, 9. Write sort((a, b) => a - b). Python sorted and Craykon Sort() order a list of numbers by size (but in Craykon, if you forget ToNumber and store strings, you get dictionary order just the same). Trap two: if you do not remove repeated pages, 5, 5, 6, 7 breaks the 'previous + 1' test and comes out as 5, 5-7. Put the pages in a set, or sort and skip a number equal to the one before. Trap three: do not shorten the pair 5, 6 to 5-6. Shorten only when the run has 3 or more pages. Trap four: if you write it as 'emit the run when it breaks', you must emit the last run once more after the loop. Forget it and the last entry of every line disappears.
Pythonmain.py · 35 lines
import sysdef page_parts(pages): """정렬되고 겹치지 않는 쪽 번호를 '3', '5-7' 같은 조각으로 바꾼다.""" parts = [] i = 0 while i < len(pages): j = i while j + 1 < len(pages) and pages[j + 1] == pages[j] + 1: j += 1 if j - i >= 2: # 셋 이상 이어질 때만 범위로 줄인다 parts.append(f"{pages[i]}-{pages[j]}") else: parts.extend(str(p) for p in pages[i : j + 1]) i = j + 1 return partsdef main(): data = sys.stdin.read().split() n = int(data[0]) index = {} for i in range(n): word, page = data[1 + 2 * i], int(data[2 + 2 * i]) index.setdefault(word, set()).add(page) # 집합이라 같은 쪽은 한 번만 남는다 lines = [] for word in sorted(index): parts = page_parts(sorted(index[word])) lines.append(word + ": " + ", ".join(parts)) # join은 '사이'에만 넣는다 print("\n".join(lines))main()
JavaScriptmain.js · 36 lines
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter((s) => s !== "");const n = Number(data[0]);// 낱말 → 쪽 번호 집합(Set이라 같은 쪽은 한 번만 남는다)const index = new Map();for (let i = 0; i < n; i++) { const word = data[1 + 2 * i]; const page = Number(data[2 + 2 * i]); if (!index.has(word)) index.set(word, new Set()); index.get(word).add(page);}// 정렬되고 겹치지 않는 쪽 번호를 "3", "5-7" 같은 조각으로 바꾼다function pageParts(pages) { const parts = []; let i = 0; while (i < pages.length) { let j = i; while (j + 1 < pages.length && pages[j + 1] === pages[j] + 1) j++; if (j - i >= 2) { parts.push(`${pages[i]}-${pages[j]}`); // 셋 이상 이어질 때만 범위로 줄인다 } else { for (let t = i; t <= j; t++) parts.push(String(pages[t])); } i = j + 1; } return parts;}const lines = [];for (const word of [...index.keys()].sort()) { // 수는 비교 함수를 줘야 크기 순이 된다(그냥 sort()는 문자열로 바꿔 견준다) const pages = [...index.get(word)].sort((a, b) => a - b); lines.push(word + ": " + pageParts(pages).join(", "));}console.log(lines.join("\n"));
TypeScriptmain.ts · 42 lines
import { readFileSync } from "node:fs";const data: string[] = readFileSync(0, "utf8").split(/\s+/).filter((s) => s !== "");const n = Number(data[0]);// 낱말 → 쪽 번호 집합(Set이라 같은 쪽은 한 번만 남는다)const index = new Map<string, Set<number>>();for (let i = 0; i < n; i++) { const word = data[1 + 2 * i]; const page = Number(data[2 + 2 * i]); let pages = index.get(word); if (pages === undefined) { pages = new Set<number>(); index.set(word, pages); } pages.add(page);}// 정렬되고 겹치지 않는 쪽 번호를 "3", "5-7" 같은 조각으로 바꾼다function pageParts(pages: number[]): string[] { const parts: string[] = []; let i = 0; while (i < pages.length) { let j = i; while (j + 1 < pages.length && pages[j + 1] === pages[j] + 1) j++; if (j - i >= 2) { parts.push(`${pages[i]}-${pages[j]}`); // 셋 이상 이어질 때만 범위로 줄인다 } else { for (let t = i; t <= j; t++) parts.push(String(pages[t])); } i = j + 1; } return parts;}const lines: string[] = [];for (const [word, set] of [...index.entries()].sort((a, b) => (a[0] < b[0] ? -1 : 1))) { // 수는 비교 함수를 줘야 크기 순이 된다(그냥 sort()는 문자열로 바꿔 견준다) const pages = [...set].sort((a, b) => a - b); lines.push(word + ": " + pageParts(pages).join(", "));}console.log(lines.join("\n"));
JavaMain.java · 50 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.Map;import java.util.StringTokenizer;import java.util.TreeMap;import java.util.TreeSet;public class Main { // 정렬되고 겹치지 않는 쪽 번호를 "3", "5-7" 같은 조각으로 바꾼다 static List<String> pageParts(List<Integer> pages) { List<String> parts = new ArrayList<>(); int i = 0; while (i < pages.size()) { int j = i; while (j + 1 < pages.size() && pages.get(j + 1) == pages.get(j) + 1) j++; if (j - i >= 2) { parts.add(pages.get(i) + "-" + pages.get(j)); // 셋 이상 이어질 때만 범위로 줄인다 } else { for (int t = i; t <= j; t++) parts.add(String.valueOf(pages.get(t))); } i = j + 1; } return parts; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); // TreeMap·TreeSet은 넣기만 해도 정렬되고, 집합이라 같은 쪽은 한 번만 남는다 TreeMap<String, TreeSet<Integer>> index = new TreeMap<>(); for (int i = 0; i < n; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); String word = st.nextToken(); int page = Integer.parseInt(st.nextToken()); index.computeIfAbsent(word, k -> new TreeSet<>()).add(page); } StringBuilder sb = new StringBuilder(); for (Map.Entry<String, TreeSet<Integer>> e : index.entrySet()) { List<String> parts = pageParts(new ArrayList<>(e.getValue())); // String.join은 문자열만 받는다(수는 먼저 문자열로 바꿔 둔다) sb.append(e.getKey()).append(": ").append(String.join(", ", parts)).append('\n'); } System.out.print(sb); }}
C#Main.cs · 54 lines
using System;using System.Collections.Generic;using System.Text;class Program{ // 정렬되고 겹치지 않는 쪽 번호를 "3", "5-7" 같은 조각으로 바꾼다 static List<string> PageParts(List<int> pages) { var parts = new List<string>(); int i = 0; while (i < pages.Count) { int j = i; while (j + 1 < pages.Count && pages[j + 1] == pages[j] + 1) j++; if (j - i >= 2) { parts.Add($"{pages[i]}-{pages[j]}"); // 셋 이상 이어질 때만 범위로 줄인다 } else { for (int t = i; t <= j; t++) parts.Add(pages[t].ToString()); } i = j + 1; } return parts; } static void Main() { int n = int.Parse(Console.ReadLine()); // SortedDictionary·SortedSet은 넣기만 해도 정렬되고, 집합이라 같은 쪽은 한 번만 남는다 var index = new SortedDictionary<string, SortedSet<int>>(StringComparer.Ordinal); for (int i = 0; i < n; i++) { string[] t = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); if (!index.TryGetValue(t[0], out var pages)) { pages = new SortedSet<int>(); index[t[0]] = pages; } pages.Add(int.Parse(t[1])); } var sb = new StringBuilder(); foreach (var e in index) { List<string> parts = PageParts(new List<int>(e.Value)); sb.Append(e.Key).Append(": ").Append(string.Join(", ", parts)).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 51 lines
#include <iostream>#include <map>#include <set>#include <string>#include <vector>using namespace std;// 정렬되고 겹치지 않는 쪽 번호를 "3", "5-7" 같은 조각으로 바꾼다vector<string> pageParts(const vector<int>& pages) { vector<string> parts; size_t i = 0; while (i < pages.size()) { size_t j = i; while (j + 1 < pages.size() && pages[j + 1] == pages[j] + 1) j++; if (j - i >= 2) { parts.push_back(to_string(pages[i]) + "-" + to_string(pages[j])); // 셋 이상만 범위로 } else { for (size_t t = i; t <= j; t++) parts.push_back(to_string(pages[t])); } i = j + 1; } return parts;}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; // map·set은 넣기만 해도 정렬되고, set이라 같은 쪽은 한 번만 남는다 map<string, set<int>> index; for (int i = 0; i < n; i++) { string word; int page; cin >> word >> page; index[word].insert(page); } for (const auto& [word, pageSet] : index) { vector<string> parts = pageParts(vector<int>(pageSet.begin(), pageSet.end())); // std::string에는 join이 없으니 '첫 조각이 아니면 앞에 쉼표'로 잇는다 string line = word + ": "; for (size_t t = 0; t < parts.size(); t++) { if (t > 0) line += ", "; line += parts[t]; } cout << line << '\n'; } return 0;}
Cmain.c · 62 lines
#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct { char word[11]; int page;} Entry;// 낱말 순, 같은 낱말이면 쪽 번호 순static int cmp(const void *a, const void *b) { const Entry *x = a, *y = b; int c = strcmp(x->word, y->word); if (c != 0) return c; return (x->page > y->page) - (x->page < y->page);}int main(void) { int n; if (scanf("%d", &n) != 1) return 1; Entry *e = malloc(sizeof(Entry) * n); for (int i = 0; i < n; i++) scanf("%10s %d", e[i].word, &e[i].page); // C에는 사전이 없으니 정렬해서 같은 낱말을 한데 모은다 qsort(e, n, sizeof(Entry), cmp); int *pages = malloc(sizeof(int) * n); int i = 0; while (i < n) { // 같은 낱말의 쪽 번호를 겹치지 않게 모은다 int cnt = 0, k = i; while (k < n && strcmp(e[k].word, e[i].word) == 0) { if (cnt == 0 || pages[cnt - 1] != e[k].page) pages[cnt++] = e[k].page; k++; } printf("%s: ", e[i].word); // join이 없으니 '첫 조각이 아니면 앞에 쉼표'로 사이에만 넣는다 int first = 1; int a = 0; while (a < cnt) { int b = a; while (b + 1 < cnt && pages[b + 1] == pages[b] + 1) b++; if (b - a >= 2) { // 셋 이상 이어질 때만 범위로 줄인다 printf(first ? "%d-%d" : ", %d-%d", pages[a], pages[b]); first = 0; } else { for (int t = a; t <= b; t++) { printf(first ? "%d" : ", %d", pages[t]); first = 0; } } a = b + 1; } printf("\n"); i = k; } free(pages); free(e); return 0;}
Craykonmain.cray · 55 lines
n = Console.ReadLine().Trim().ToNumber();// 낱말 → 쪽 번호 목록index = Dict();for (i = 0; i < n; i++){ t = Console.ReadLine().Trim().Split(); if (!index.Contains(t[0])) { index[t[0]] = []; } index[t[0]].Add(t[1].ToNumber()); // 수로 바꿔 넣어야 크기 순으로 정렬된다}words = index.Keys;words.Sort();foreach (word in words){ all = index[word]; all.Sort(); // 같은 쪽은 한 번만 남긴다(정렬했으니 바로 앞과만 견주면 된다) pages = []; foreach (p in all) { if (pages.Count == 0 || pages[pages.Count - 1] != p) { pages.Add(p); } } parts = []; i = 0; while (i < pages.Count) { j = i; while (j + 1 < pages.Count && pages[j + 1] == pages[j] + 1) { j++; } if (j - i >= 2) { parts.Add(pages[i] + "-" + pages[j]); // 셋 이상 이어질 때만 범위로 줄인다 } else { for (k = i; k <= j; k++) { parts.Add(pages[k]); } } i = j + 1; } Console.WriteLine(word + ": " + parts.Join(", ")); // 잇기는 '사이'에만 넣는다}