종이 사전은 쪽마다 맨 위에 그 쪽의 첫 낱말과 마지막 낱말을 적어 둔다.
이 두 낱말을 길잡이 낱말이라고 한다.
사전 p쪽에 실린 낱말들이 쪽마다 뒤섞인 순서로 주어진다.
낱말의 앞뒤는 글자 코드 순서로 정한다.
두 낱말을 앞에서부터 한 글자씩 견주어 처음으로 다른 글자의 코드가 작은 쪽이 앞이고, 한 낱말이 다른 낱말의 앞부분과 똑같으면 짧은 쪽이 앞이다.
글자 코드는 붙임표(-)가 가장 작고, 그다음이 대문자 A~Z, 그다음이 소문자 a~z이다.
먼저 쪽마다 그 쪽에서 가장 앞인 낱말과 가장 뒤인 낱말, 곧 길잡이 낱말을 찾는다.
그런 다음 찾을 낱말 q개가 주어지면, 낱말마다 그 낱말이 실려 있어야 할 쪽 번호를 구한다.
찾을 낱말이 i쪽의 가장 앞 낱말과 같거나 그보다 뒤이고, i쪽의 가장 뒤 낱말과 같거나 그보다 앞이면 그 낱말이 실려 있어야 할 쪽은 i쪽이다.
입력
첫 줄에 쪽 수 p가 주어진다(1 ≤ p ≤ 100).
다음 p개 줄의 i번째 줄에 i쪽의 낱말 수 k와 낱말 k개가 빈칸 하나로 띄워 주어진다(1 ≤ k ≤ 50).
낱말은 영어 대문자, 소문자, 붙임표(-)로만 이루어진 길이 1 이상 15 이하의 문자열이다.
사전의 모든 낱말은 서로 다르다.
i쪽의 모든 낱말은 i+1쪽의 모든 낱말보다 앞이다.
다음 줄에 찾을 낱말 수 q가 주어진다(1 ≤ q ≤ 1,000).
다음 q개 줄에 찾을 낱말이 한 줄에 하나씩 주어진다.
찾을 낱말도 같은 글자들로 이루어진 길이 1 이상 15 이하의 문자열이고, 사전에 없는 낱말일 수도 있다.
출력
처음 p개 줄의 i번째 줄에 i쪽의 가장 앞 낱말과 가장 뒤 낱말을 빈칸 하나로 띄워 출력한다.
낱말이 하나뿐인 쪽은 그 낱말을 두 번 출력한다.
다음 q개 줄에 찾을 낱말마다 실려 있어야 할 쪽 번호를 주어진 순서대로 한 줄에 하나씩 출력한다.
그런 쪽이 없으면 0을 출력한다.
예시 1 · stdin
3
3 Io IT Ice
4 cat apple banana app
1 zebra
6
apple
Io
app
ant
zebra
Ice
stdout
IT Io
app cat
zebra zebra
2
1
2
0
3
1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
문자열의 앞뒤를 견주는 방법과 여럿 가운데 가장 앞인 것을 고르는 방법이 언어마다 달라요.
Python은 <, <=와 min(), max()가 문자열에 그대로 통하고 코드 순서로 견줘요. first <= w <= last처럼 비교를 이어 쓸 수도 있어요.
JavaScript·TypeScript도 문자열끼리 <가 코드 순서예요. 하지만 Math.min("b", "a")는 NaN이라서(TypeScript는 타입 오류) 가장 앞 낱말은 반복문으로 직접 찾아요. localeCompare는 로캘 순서라서 "IT"와 "Ice"의 앞뒤가 <와 반대로 나와요.
Java와 C#은 문자열에 <를 쓰면 컴파일 오류예요. Java는 a.compareTo(b)의 부호를 보고, Collections.min()도 같은 순서를 써요. C#은 string.CompareOrdinal(a, b)가 코드 순서이고, string.Compare, CompareTo, LINQ의 Min()·Max()는 문화권 순서예요.
C는 strcmp(a, b)의 부호를 보고, C++은 std::string에 <를 그대로 쓰며 minmax_element로 둘을 한꺼번에 찾을 수 있어요.
크레이콘도 문자열끼리 <가 코드 순서예요.
함정 하나: 이어 쓴 비교예요. JavaScript에서 first <= w <= last는 오류 없이 돌아가지만, 앞의 비교가 먼저 true나 false가 되고 그 값을 낱말과 견줄 때 낱말이 수로 바뀌어 NaN이 되므로 false가 돼요. 예시 1의 찾을 낱말 여섯 개에 모두 0을 출력해요. TypeScript는 이 식을 타입 오류로, 크레이콘은 컴파일 오류로 막아 줘요.
함정 둘: 문화권 순서예요. 예시 1의 1쪽 Io IT Ice는 코드 순서로 IT, Ice, Io예요(대문자 T가 소문자 c보다 앞). C#의 Min()·Max()는 Ice, Io, IT 순서로 보아서 IT Io가 아니라 Ice IT를 출력해요.
함정 셋: 대소문자를 무시하는 비교예요. Java의 compareToIgnoreCase로 견주어도 같은 줄에서 Ice IT가 나와요.
함정 넷: 길잡이 낱말과 같은 낱말이에요. 예시 1의 Io와 app은 길잡이 낱말 그 자체라서 <=가 아니라 <로 견주면 0이 나와요. 낱말이 하나뿐인 3쪽의 zebra도 그래요.
함정 다섯: 쪽마다 새로 시작하기예요. 가장 앞 낱말을 담는 변수를 쪽마다 새로 시작하지 않으면 뒤쪽 낱말이 모두 더 뒤라서 1쪽의 것이 그대로 남아요. 예시 1의 2쪽이 app cat이 아니라 IT cat으로 나와요.
Pythonmain.py · 26 줄
import syslines = sys.stdin.read().split("\n")p = int(lines[0])firsts = []lasts = []out = []for i in range(1, p + 1): words = lines[i].split()[1:] # 문자열 비교(<, min, max)는 글자 코드 순서다 first = min(words) last = max(words) firsts.append(first) lasts.append(last) out.append(first + " " + last)q = int(lines[p + 1])for j in range(q): w = lines[p + 2 + j].strip() page = 0 for i in range(p): if firsts[i] <= w <= lasts[i]: # 파이썬은 비교를 이어 쓸 수 있다 page = i + 1 break out.append(str(page))print("\n".join(out))
JavaScriptmain.js · 32 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const p = Number(lines[0]);const firsts = [];const lasts = [];const out = [];for (let i = 1; i <= p; i++) { const words = lines[i].trim().split(" ").slice(1); // 문자열끼리 <는 코드 순서다(Math.min은 문자열에 쓸 수 없다) let first = words[0]; let last = words[0]; for (const w of words) { if (w < first) first = w; if (w > last) last = w; } firsts.push(first); lasts.push(last); out.push(first + " " + last);}const q = Number(lines[p + 1]);for (let j = 0; j < q; j++) { const w = lines[p + 2 + j].trim(); let page = 0; for (let i = 0; i < p; i++) { if (firsts[i] <= w && w <= lasts[i]) { page = i + 1; break; } } out.push(String(page));}console.log(out.join("\n"));
TypeScriptmain.ts · 34 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const p: number = Number(lines[0]);const firsts: string[] = [];const lasts: string[] = [];const out: string[] = [];for (let i = 1; i <= p; i++) { const words: string[] = lines[i].trim().split(" ").slice(1); // 문자열끼리 <는 코드 순서다(Math.min은 문자열을 받지 않는다) let first: string = words[0]; let last: string = words[0]; for (const w of words) { if (w < first) first = w; if (w > last) last = w; } firsts.push(first); lasts.push(last); out.push(first + " " + last);}const q: number = Number(lines[p + 1]);for (let j = 0; j < q; j++) { const w: string = lines[p + 2 + j].trim(); let page: number = 0; for (let i = 0; i < p; i++) { if (firsts[i] <= w && w <= lasts[i]) { page = i + 1; break; } } out.push(String(page));}console.log(out.join("\n"));
JavaMain.java · 40 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int p = Integer.parseInt(br.readLine().trim()); String[] firsts = new String[p]; String[] lasts = new String[p]; StringBuilder sb = new StringBuilder(); for (int i = 0; i < p; i++) { String[] parts = br.readLine().trim().split(" "); // 문자열에는 <가 없다: compareTo가 코드 순서로 견준다 String first = parts[1]; String last = parts[1]; for (int j = 2; j < parts.length; j++) { if (parts[j].compareTo(first) < 0) first = parts[j]; if (parts[j].compareTo(last) > 0) last = parts[j]; } firsts[i] = first; lasts[i] = last; sb.append(first).append(' ').append(last).append('\n'); } int q = Integer.parseInt(br.readLine().trim()); for (int j = 0; j < q; j++) { String w = br.readLine().trim(); int page = 0; for (int i = 0; i < p; i++) { if (firsts[i].compareTo(w) <= 0 && w.compareTo(lasts[i]) <= 0) { page = i + 1; break; } } sb.append(page).append('\n'); } System.out.print(sb); }}
C#Main.cs · 45 줄
using System;using System.Text;class Program{ static void Main() { int p = int.Parse(Console.ReadLine().Trim()); string[] firsts = new string[p]; string[] lasts = new string[p]; StringBuilder sb = new StringBuilder(); for (int i = 0; i < p; i++) { string[] parts = Console.ReadLine().Trim().Split(' '); // CompareOrdinal이 코드 순서다(Compare, CompareTo, Min()은 문화권 순서) string first = parts[1]; string last = parts[1]; for (int j = 2; j < parts.Length; j++) { if (string.CompareOrdinal(parts[j], first) < 0) first = parts[j]; if (string.CompareOrdinal(parts[j], last) > 0) last = parts[j]; } firsts[i] = first; lasts[i] = last; sb.Append(first).Append(' ').Append(last).Append('\n'); } int q = int.Parse(Console.ReadLine().Trim()); for (int j = 0; j < q; j++) { string w = Console.ReadLine().Trim(); int page = 0; for (int i = 0; i < p; i++) { if (string.CompareOrdinal(firsts[i], w) <= 0 && string.CompareOrdinal(w, lasts[i]) <= 0) { page = i + 1; break; } } sb.Append(page).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 40 줄
#include <algorithm>#include <iostream>#include <string>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int p; cin >> p; vector<string> firsts(p), lasts(p); for (int i = 0; i < p; i++) { int k; cin >> k; vector<string> words(k); for (auto& w : words) cin >> w; // std::string의 <는 코드 순서다 auto [lo, hi] = minmax_element(words.begin(), words.end()); firsts[i] = *lo; lasts[i] = *hi; cout << firsts[i] << ' ' << lasts[i] << '\n'; } int q; cin >> q; for (int j = 0; j < q; j++) { string w; cin >> w; int page = 0; for (int i = 0; i < p; i++) { if (firsts[i] <= w && w <= lasts[i]) { page = i + 1; break; } } cout << page << '\n'; } return 0;}
Cmain.c · 38 줄
#include <stdio.h>#include <string.h>static char firsts[100][16];static char lasts[100][16];int main(void) { int p; if (scanf("%d", &p) != 1) return 1; for (int i = 0; i < p; i++) { int k; char w[16]; if (scanf("%d", &k) != 1) return 1; for (int j = 0; j < k; j++) { if (scanf("%15s", w) != 1) return 1; /* strcmp는 부호만 믿는다: 음수면 앞, 양수면 뒤 */ if (j == 0 || strcmp(w, firsts[i]) < 0) strcpy(firsts[i], w); if (j == 0 || strcmp(w, lasts[i]) > 0) strcpy(lasts[i], w); } printf("%s %s\n", firsts[i], lasts[i]); } int q; if (scanf("%d", &q) != 1) return 1; for (int j = 0; j < q; j++) { char w[16]; if (scanf("%15s", w) != 1) return 1; int page = 0; for (int i = 0; i < p; i++) { if (strcmp(firsts[i], w) <= 0 && strcmp(w, lasts[i]) <= 0) { page = i + 1; break; } } printf("%d\n", page); } return 0;}
Craykonmain.cray · 41 줄
쪽수 = 콘솔.줄읽기().수로변환();첫낱말들 = [];끝낱말들 = [];반복 (i = 0; i < 쪽수; i++){ 칸들 = 콘솔.줄읽기().공백제거().나누기(); // 문자열끼리 <는 코드 순서다 첫낱말 = 칸들[1]; 끝낱말 = 칸들[1]; 반복 (j = 2; j < 칸들.개수; j++) { 만약 (칸들[j] < 첫낱말) { 첫낱말 = 칸들[j]; } 만약 (칸들[j] > 끝낱말) { 끝낱말 = 칸들[j]; } } 첫낱말들.넣기(첫낱말); 끝낱말들.넣기(끝낱말); 콘솔.쓰기(첫낱말 + " " + 끝낱말);}찾을수 = 콘솔.줄읽기().수로변환();반복 (j = 0; j < 찾을수; j++){ 낱말 = 콘솔.줄읽기().공백제거(); 쪽 = 0; 반복 (i = 0; i < 쪽수; i++) { // 첫낱말들[i] <= 낱말 <= 끝낱말들[i]처럼 이어 쓰면 컴파일 오류다 만약 (첫낱말들[i] <= 낱말 && 낱말 <= 끝낱말들[i]) { 쪽 = i + 1; 그만; } } 콘솔.쓰기(쪽);}