질의식 처리(LINQ·스트림)P0263

중고 장터 검색 창

중고 장터에 물건 n개가 올라와 있고, 검색 질문 q개에 차례로 답한다. 물건마다 이름, 종류, 가격이 있다. 질문 "종류 최대가격 k"는 그 종류이면서 가격이 최대가격 이하인 물건을 고르라는 뜻이다.
종류가 *이면 종류와 상관없이 모든 물건에서 고른다. 질문마다 한 줄에, 고른 물건의 수 c를 먼저 쓰고 이어서 고른 물건 가운데 앞에서부터 k개의 이름을 빈칸 하나씩 띄워 출력하라. 고른 물건은 가격이 싼 것이 앞이고, 가격이 같으면 이름의 사전 순(문자 코드 순이라 숫자가 영어 소문자보다 앞이고, ab는 abc보다 앞)으로 앞이다. c가 k보다 작으면 c개를 모두 쓰고, c가 0이면 0만 출력한다. 가격은 쉼표 없이 숫자만 주어지고, 출력도 숫자만 쓴다. 첫 줄에 n과 q, 다음 n줄에 물건이 "이름 종류 가격"으로, 그다음 q줄에 질문이 하나씩 주어진다. 반복문 대신 거르기 → 정렬 → 앞에서 k개 → 이름만 뽑기를 잇는 질의식 처리로 풀어 보자.

입력: 1 ≤ n ≤ 1,000, 1 ≤ q ≤ 1,000, 1 ≤ k ≤ 10.
물건 이름은 영어 소문자·숫자 1~10글자이고 서로 다르다.
종류는 영어 소문자 1~10글자다(질문의 종류는 물건에 없는 종류일 수도 있다).
1 ≤ 가격, 최대가격 ≤ 1,000,000,000(정수)
출력: 질문마다 한 줄

예시 1 · stdin

6 4
lamp9 lamp 12000
bluebike bike 85000
redbike bike 85000
kidbike bike 30000
oldlamp lamp 9000
citybike bike 120000
bike 90000 2
lamp 5000 3
* 12000 5
bike 1000000000 10

stdout

3 kidbike bluebike
0
2 oldlamp lamp9
4 kidbike bluebike redbike citybike

main.py 프로그래밍 언어 실행 판

입력(stdin)

실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).

$ 준비됐어요

코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.

다른 언어로는?언어별 풀이 보기 · 6개 언어 풀이

이 문제는 거르기·정렬·자르기·뽑기를 잇는 도구가 언어에 들어 있는 Python(목록 내포·sorted)·JavaScript·TypeScript(배열 메서드)·Java(스트림)·C#(LINQ)·C++(C++20 std::views)만 받아요.
C와 크레이콘에는 함수를 받아 거르고 바꾸는 목록 도구가 없어요.
같은 일을 Python [it for it in items if ...] → sorted(key=lambda it: (it.price, it.name))[:k], JS·TS filter → sort → slice → map, Java filter → toList() 뒤 sorted → limit → map, C# Where → ToList() 뒤 OrderBy → ThenBy → Take → Select, C++ items | std::views::filter(...)를 vector에 받아 std::ranges::sort 뒤 std::views::take(k)로 써요.
개수와 이름 목록에 거른 결과를 두 번 쓰는 게 이 문제의 함정이에요.
① Python filter()·map()은 한 번 돌면 비는 반복자라서, 개수를 세느라 다 돌면 sorted가 빈 것을 받아요.
목록 내포나 list(...)로 받아 두어요.
② Java 스트림도 한 번만 흘려보낼 수 있어서, 스트림 변수로 count()한 뒤 다시 sorted()하면 IllegalStateException이 나요.
toList()로 받아 두고 필요할 때 새로 stream()해요.
C# LINQ는 반대로 게을러서, ToList() 없이 두 번 쓰면 오류는 없지만 쓸 때마다 처음부터 다시 걸러요.
③ C# OrderBy(...).OrderBy(...)는 두 번째 OrderBy가 새 첫 기준이 되어 이름 순으로 다시 늘어놓아요(앞의 가격은 이름이 같을 때만 따지는데, 이름은 서로 달라요).
두 번째 기준은 ThenBy(Java thenComparing)로 이어요.
이름 순은 StringComparer.Ordinal을 주면 문자 코드 순이 확실해요.
④ JS는 split이 준 가격이 문자열이라 Number()를 빠뜨리면 "100" <= "99"가 참이 되는 사전 순 비교를 해요.
TypeScript는 price: number인 타입에 문자열을 넣으면 타입 오류로 잡아 줘요.
⑤ 가격만으로 정렬하면 같은 가격이 입력 차례로 남아요.
두 기준을 함께 줘요.
덤으로 C++ std::views::filter는 게으른 보기라 바로 정렬할 수 없고(임의 접근이 안 돼요), JS sort는 그 배열을 그 자리에서 바꾸지만 filter가 새 배열을 주니 원래 목록은 그대로예요.

Pythonmain.py · 22 줄

import sysfrom collections import namedtuple Item = namedtuple("Item", "name kind price") lines = sys.stdin.read().split("\n")n, q = map(int, lines[0].split())items = []for line in lines[1 : n + 1]:    name, kind, price = line.split()    items.append(Item(name, kind, int(price))) out = []for line in lines[n + 1 : n + 1 + q]:    kind, limit, k = line.split()    limit, k = int(limit), int(k)    # 거르기: 목록 내포는 목록을 만들어 두므로 개수를 센 뒤에도 다시 쓸 수 있다    picked = [it for it in items if (kind == "*" or it.kind == kind) and it.price <= limit]    # 정렬 → 앞에서 k개 → 이름만    top = [it.name for it in sorted(picked, key=lambda it: (it.price, it.name))[:k]]    out.append(" ".join([str(len(picked))] + top))print("\n".join(out))

JavaScriptmain.js · 19 줄

const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(" ").map(Number);const items = lines.slice(1, n + 1).map((line) => {  const [name, kind, price] = line.trim().split(" ");  return { name, kind, price: Number(price) }; // Number가 없으면 가격이 문자열로 비교된다}); const byPriceThenName = (a, b) => a.price - b.price || (a.name < b.name ? -1 : a.name > b.name ? 1 : 0); const out = [];for (const line of lines.slice(n + 1, n + 1 + q)) {  const [kind, limitText, kText] = line.trim().split(" ");  const limit = Number(limitText);  const picked = items.filter((it) => (kind === "*" || it.kind === kind) && it.price <= limit);  // filter는 새 배열을 주므로 sort가 picked를 바꾸어도 items는 그대로다  const top = picked.sort(byPriceThenName).slice(0, Number(kText)).map((it) => it.name);  out.push([picked.length, ...top].join(" "));}console.log(out.join("\n"));

TypeScriptmain.ts · 26 줄

import { readFileSync } from "node:fs"; interface Item {  name: string;  kind: string;  price: number;} const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(" ").map(Number);const items: Item[] = lines.slice(1, n + 1).map((line) => {  const [name, kind, price] = line.trim().split(" ");  return { name, kind, price: Number(price) }; // Item 타입이 price를 number로 요구해서 Number를 빠뜨리면 타입 오류다}); const byPriceThenName = (a: Item, b: Item): number => a.price - b.price || (a.name < b.name ? -1 : a.name > b.name ? 1 : 0); const out: string[] = [];for (const line of lines.slice(n + 1, n + 1 + q)) {  const [kind, limitText, kText] = line.trim().split(" ");  const limit = Number(limitText);  const picked: Item[] = items.filter((it) => (kind === "*" || it.kind === kind) && it.price <= limit);  const top: string[] = picked.sort(byPriceThenName).slice(0, Number(kText)).map((it) => it.name);  out.push([picked.length, ...top].join(" "));}console.log(out.join("\n"));

JavaMain.java · 40 줄

import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Comparator;import java.util.List;import java.util.stream.Collectors; public class Main {    record Item(String name, String kind, long price) {}     public static void main(String[] args) throws Exception {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        String[] first = in.readLine().trim().split(" ");        int n = Integer.parseInt(first[0]), q = Integer.parseInt(first[1]);        List<Item> items = new ArrayList<>();        for (int i = 0; i < n; i++) {            String[] p = in.readLine().trim().split(" ");            items.add(new Item(p[0], p[1], Long.parseLong(p[2])));        }        Comparator<Item> byPriceThenName = Comparator.comparingLong(Item::price).thenComparing(Item::name);        StringBuilder out = new StringBuilder();        for (int i = 0; i < q; i++) {            String[] p = in.readLine().trim().split(" ");            String kind = p[0];            long limit = Long.parseLong(p[1]);            int k = Integer.parseInt(p[2]);            // 스트림은 한 번만 흘려보낼 수 있다: 거른 결과를 목록으로 받아 두고 두 번 쓴다            List<Item> picked = items.stream()                    .filter(it -> (kind.equals("*") || it.kind().equals(kind)) && it.price() <= limit)                    .toList();            String top = picked.stream()                    .sorted(byPriceThenName)                    .limit(k)                    .map(it -> " " + it.name())                    .collect(Collectors.joining());            out.append(picked.size()).append(top).append('\n');        }        System.out.print(out);    }}

C#Main.cs · 37 줄

using System;using System.Collections.Generic;using System.Linq;using System.Text; record Item(string Name, string Kind, long Price); class Program{    static void Main()    {        int[] first = Console.ReadLine()!.Trim().Split(' ').Select(int.Parse).ToArray();        int n = first[0], q = first[1];        List<Item> items = Enumerable.Range(0, n)            .Select(_ => Console.ReadLine()!.Trim().Split(' '))            .Select(p => new Item(p[0], p[1], long.Parse(p[2])))            .ToList();        var sb = new StringBuilder();        for (int i = 0; i < q; i++)        {            string[] p = Console.ReadLine()!.Trim().Split(' ');            string kind = p[0];            long limit = long.Parse(p[1]);            int k = int.Parse(p[2]);            List<Item> picked = items                .Where(it => (kind == "*" || it.Kind == kind) && it.Price <= limit)                .ToList(); // ToList로 한 번 계산해 둔다(그냥 두면 쓸 때마다 다시 거른다)            IEnumerable<string> top = picked                .OrderBy(it => it.Price)                .ThenBy(it => it.Name, StringComparer.Ordinal) // 두 번째 기준은 OrderBy가 아니라 ThenBy                .Take(k)                .Select(it => it.Name);            sb.Append(string.Join(" ", top.Prepend(picked.Count.ToString()))).Append('\n');        }        Console.Write(sb);    }}

C++main.cpp · 38 줄

#include <algorithm>#include <iostream>#include <ranges>#include <string>#include <tuple>#include <vector> struct Item {    std::string name, kind;    long long price;}; int main() {    std::ios::sync_with_stdio(false);    int n, q;    std::cin >> n >> q;    std::vector<Item> items(n);    for (auto& it : items) std::cin >> it.name >> it.kind >> it.price;     auto byPriceThenName = [](const Item& a, const Item& b) {        return std::tie(a.price, a.name) < std::tie(b.price, b.name);    };    for (int i = 0; i < q; i++) {        std::string kind;        long long limit;        int k;        std::cin >> kind >> limit >> k;        // views::filter는 게으른 보기(view)라서 정렬할 수 없다: vector로 받아 둔다        auto view = items | std::views::filter([&](const Item& it) {                        return (kind == "*" || it.kind == kind) && it.price <= limit;                    });        std::vector<Item> picked(view.begin(), view.end());        std::ranges::sort(picked, byPriceThenName);        std::cout << picked.size();        for (const Item& it : picked | std::views::take(k)) std::cout << ' ' << it.name;        std::cout << '\n';    }}