책 끝에 붙는 찾아보기를 만들려고 한다.
낱말과 그 낱말이 나온 쪽 번호를 적은 기록이 n줄 주어진다.
같은 낱말이 여러 줄에 나올 수 있고, 같은 낱말과 같은 쪽 번호가 적힌 줄이 여러 번 나올 수도 있다.
낱말마다 한 줄씩, 낱말, 쌍점(:), 빈칸 하나, 쪽 목록을 차례로 붙여 출력하라.
낱말은 알파벳 사전 순으로 출력한다(앞부분이 같으면 짧은 낱말이 먼저다).
쪽 목록은 다음처럼 만든다.
한 낱말의 쪽 번호는 겹친 것을 하나만 남기고 작은 수부터 늘어놓는다.
늘어놓은 쪽 번호를 앞에서부터 묶음으로 나눈다. 바로 앞 쪽 번호보다 꼭 1 큰 쪽 번호는 앞 쪽 번호와 같은 묶음에 들고, 그렇지 않은 쪽 번호에서 새 묶음이 시작된다.
쪽 번호가 셋 이상인 묶음은 "첫 쪽-끝 쪽"으로 줄여 쓴다(5, 6, 7은 5-7이고, 5, 6, 7, 8은 5-8).
쪽 번호가 둘인 묶음은 줄이지 않고 두 쪽 번호를 따로 쓴다(5, 6은 그대로 5와 6). 쪽 번호가 하나인 묶음은 그 쪽 번호를 쓴다.
이렇게 만든 항목 사이마다 쉼표와 빈칸 하나(", ")를 넣는다.
줄 끝에는 쉼표나 빈칸을 붙이지 않는다.
입력
첫 줄에 n이 주어진다. 다음 n줄에 낱말과 쪽 번호가 빈칸 하나로 나뉘어 주어진다. 1 ≤ n ≤ 5,000, 낱말은 영어 소문자로만 된 길이 1~10의 문자열, 1 ≤ 쪽 번호 ≤ 100,000
출력
서로 다른 낱말마다 한 줄. "낱말: 쪽 목록" 꼴이며, 쪽 번호는 쉼표 없이 숫자만 쓴다(100000)
예시 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
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
항목 '사이'에만 구분 문자열을 넣는 일이 join이에요. Python ", ".join(parts), JS·TS parts.join(", "), Java String.join(", ", parts), C# string.Join(", ", parts), 크레이콘 parts.잇기(", ")처럼 한 줄이면 돼요. C에는 join이 없고 C++ std::string에도 없어서 '첫 항목이 아니면 앞에 쉼표를 찍는다'로 직접 이어요. 항목마다 뒤에 ", "를 붙이면 줄 끝에 쉼표가 남으니 조심해요. join이 받는 것도 달라요: Python은 문자열만 받아서 수가 섞이면 TypeError이고, Java String.join도 문자열 목록만 받아요(List<Integer>는 컴파일 오류). JS·TS, C#, 크레이콘은 수를 알아서 문자열로 바꿔 이어 줘요. 묶기는 사전으로 해요: Python dict+set, JS·TS Map+Set, Java TreeMap+TreeSet, C# SortedDictionary+SortedSet, C++ map+set(이 셋은 넣기만 해도 정렬돼요), 크레이콘 사전()에 목록을 담아요. C는 사전이 없으니 (낱말, 쪽)을 통째로 qsort해서 같은 낱말을 이웃하게 만들어요. 함정 하나: JS·TS의 sort()는 비교 함수가 없으면 수도 문자열로 바꿔 견줘서 9, 10, 100이 10, 100, 9가 돼요. sort((a, b) => a - b)로 써요. Python sorted, 크레이콘 정렬()은 수 목록이면 크기 순이에요(단, 크레이콘에서 수로변환을 잊고 문자열로 넣으면 똑같이 사전 순이 돼요). 함정 둘: 겹친 쪽을 지우지 않으면 5, 5, 6, 7에서 '앞 수 + 1'이 깨져 5, 5-7이 돼요. 집합에 넣거나, 정렬한 뒤 바로 앞과 같은 수를 건너뛰어요. 함정 셋: 둘만 이어진 5, 6을 5-6으로 줄이면 안 돼요. 묶음 길이가 3 이상일 때만 줄여요. 함정 넷: '이어짐이 끊길 때 묶음을 내보낸다'로 짜면 반복이 끝난 뒤 마지막 묶음을 한 번 더 내보내야 해요. 빠뜨리면 줄마다 마지막 항목이 사라져요.
Pythonmain.py · 35 줄
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 줄
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 줄
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 줄
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 줄
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 줄
#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 줄
#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 줄
n = 콘솔.줄읽기().공백제거().수로변환();// 낱말 → 쪽 번호 목록index = 사전();반복 (i = 0; i < n; i++){ t = 콘솔.줄읽기().공백제거().나누기(); 만약 (!index.있나(t[0])) { index[t[0]] = []; } index[t[0]].넣기(t[1].수로변환()); // 수로 바꿔 넣어야 크기 순으로 정렬된다}words = index.열쇠목록;words.정렬();각각 (word 에서 words){ all = index[word]; all.정렬(); // 같은 쪽은 한 번만 남긴다(정렬했으니 바로 앞과만 견주면 된다) pages = []; 각각 (p 에서 all) { 만약 (pages.개수 == 0 || pages[pages.개수 - 1] != p) { pages.넣기(p); } } parts = []; i = 0; 동안 (i < pages.개수) { j = i; 동안 (j + 1 < pages.개수 && pages[j + 1] == pages[j] + 1) { j++; } 만약 (j - i >= 2) { parts.넣기(pages[i] + "-" + pages[j]); // 셋 이상 이어질 때만 범위로 줄인다 } 아니면 { 반복 (k = i; k <= j; k++) { parts.넣기(pages[k]); } } i = j + 1; } 콘솔.쓰기(word + ": " + parts.잇기(", ")); // 잇기는 '사이'에만 넣는다}