보물찾기 놀이에서 아이 n명이 모래밭의 칸을 팠다.
모래밭의 칸은 (행, 열)로 나타내고, 보물은 (a, b) 칸에 묻혀 있다.
아이마다 판 칸이 판 차례대로 주어진다.
같은 칸을 여러 번 판 아이도 있고, 한 칸도 파지 않은 아이도 있다.
칸 (r, c)와 보물 사이의 거리는 |r - a| + |c - b|이다.
아이마다 한 줄에 이름, 그 아이가 판 서로 다른 칸의 수, 그 아이가 판 칸 가운데 보물과 가장 가까운 칸의 거리를 입력에 나온 차례대로 출력하라.
한 칸도 파지 않은 아이는 거리 자리에 -를 쓴다.
그다음 줄에 모든 아이가 판 칸을 통틀어 서로 다른 칸의 수를 출력하라.
마지막 줄에 꼼꼼한 아이의 이름을 입력에 나온 차례대로 출력하라.
꼼꼼한 아이는 한 칸 이상 팠고, 판 칸이 모두 보물과의 거리가 d 이하인 아이다.
반복문으로 하나씩 세는 대신 중복 없애기, 가장 작은 값 고르기, 모두 그런지 묻기, 목록 이어 붙이기를 잇는 질의식 처리로 풀어 보자.
입력
첫 줄에 n, a, b, d가 빈칸 하나로 나뉘어 주어진다. 다음 n줄에 줄마다 아이의 이름, 판 칸의 수 k, 이어서 판 칸의 행과 열이 k쌍 빈칸 하나로 나뉘어 주어진다. 1 ≤ n ≤ 100, 1 ≤ a, b ≤ 1000, 0 ≤ d ≤ 2000, 0 ≤ k ≤ 50, 1 ≤ r, c ≤ 1000. 이름은 영어 소문자 1~10글자이고 서로 다르다
출력
n + 2줄. 아이마다 "이름 칸수 거리"를 빈칸 하나로 띄워 쓴다. 그다음 줄에 수 하나를 쓴다. 마지막 줄에 꼼꼼한 아이의 이름을 빈칸 하나로 띄워 쓰고, 꼼꼼한 아이가 없으면 -만 쓴다
예시 1 · stdin
4 3 3 2
ann 4 3 4 2 2 3 4 3 3
bo 2 1 1 5 5
cy 0
dee 3 2 2 2 2 2 2
stdout
ann 3 0
bo 2 4
cy 0 -
dee 1 2
5
ann dee
예시 2 · stdin
2 5 5 1
zed 2 1 11 11 1
yo 1 5 7
stdout
zed 2 10
yo 1 2
3
-
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 6개 언어 풀이
이 문제는 목록을 거르고 바꾸는 도구가 언어에 들어 있는 Python·JavaScript·TypeScript·Java(스트림)·C#(LINQ)·C++(C++20 std::ranges)만 받아요. C와 크레이콘에는 함수를 받아 거르고 바꾸는 목록 도구가 없어요. 같은 일의 이름이 언어마다 달라요. 중복 없애기는 Python set(cells), JS·TS new Set(...), Java distinct(), C# Distinct(), C++ std::set이에요. 아이마다의 목록을 하나로 이어 붙이기는 Python 겹친 내포, JS·TS·Java flatMap, C# SelectMany, C++ std::views::join이에요. 모두 그런지 묻기는 all, every, allMatch, All, std::ranges::all_of이고, 가장 작은 값은 min, Math.min(...), mapToInt(...).min(), Min, std::ranges::min이에요. 요점은 '같은 칸'을 무엇으로 가리느냐예요. Python 튜플, Java record, C# 값 튜플 (int R, int C), C++ pair는 값으로 가려요. JS·TS의 Set은 객체와 배열을 '같은 객체인가'로 가려서, 풀이는 칸을 r + "," + c 문자열 열쇠로 바꿔 넣어요. 함정 하나: JS에서 칸을 [r, c] 배열 그대로 Set에 넣으면 같은 칸이 합쳐지지 않아요. 첫째 예시가 ann 4, dee 3, 합 9가 돼요. Java에서 equals가 없는 보통 클래스로, C#에서 class로 칸을 만들어도 똑같은 답이 나와요. 함정 둘: 열쇠를 구분 글자 없이 ${r}${c}로 만들면 (1, 11)과 (11, 1)이 둘 다 111이에요. 둘째 예시가 zed 1 10과 2가 돼요. 함정 셋: C++ std::unique는 바로 이웃한 같은 값만 지워요. 정렬 없이 쓰면 첫째 예시가 ann 4와 합 7이 돼요. 함정 넷: '모두 그런가'는 빈 목록에 참이에요(Python all, JS every). 판 칸이 있는지를 따로 묻지 않으면 첫째 예시의 마지막 줄이 ann cy dee가 돼요. 함정 다섯: 빈 목록의 가장 작은 값은 언어마다 달라요. Python min은 ValueError, Java getAsInt()는 NoSuchElementException, C# Min은 InvalidOperationException으로 멈춰요. JS의 인자 없는 Math.min()은 오류 없이 Infinity라서 첫째 예시의 셋째 줄이 cy 0 Infinity가 돼요.
Pythonmain.py · 25 줄
import syslines = sys.stdin.read().split("\n")n, a, b, d = map(int, lines[0].split())kids = []for i in range(1, n + 1): p = lines[i].split() nums = [int(x) for x in p[2:]] # 칸은 (행, 열) 튜플: 값이 같으면 같은 것으로 친다 kids.append((p[0], list(zip(nums[0::2], nums[1::2]))))def dist(cell): return abs(cell[0] - a) + abs(cell[1] - b)for name, cells in kids: closest = min(map(dist, cells)) if cells else "-" # 빈 것의 min은 ValueError print(name, len(set(cells)), closest)print(len({cell for _, cells in kids for cell in cells}))# all은 빈 것에 참이므로 판 칸이 있는지를 따로 묻는다careful = [name for name, cells in kids if cells and all(dist(cell) <= d for cell in cells)]print(" ".join(careful) if careful else "-")
JavaScriptmain.js · 29 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, a, b, d] = lines[0].trim().split(/\s+/).map(Number);const kids = [];for (let i = 1; i <= n; i++) { const p = lines[i].trim().split(/\s+/); const nums = p.slice(2).map(Number); const cells = []; for (let j = 0; j < nums.length; j += 2) cells.push({ r: nums[j], c: nums[j + 1] }); kids.push({ name: p[0], cells });}const dist = (cell) => Math.abs(cell.r - a) + Math.abs(cell.c - b);// Set은 객체·배열을 값이 아니라 '같은 객체인가'로 가리므로 문자열 열쇠로 바꿔 넣는다const key = (cell) => cell.r + "," + cell.c;const out = kids.map((kid) => { const distinct = new Set(kid.cells.map(key)).size; const closest = kid.cells.length ? Math.min(...kid.cells.map(dist)) : "-"; // 빈 것의 Math.min은 Infinity return `${kid.name} ${distinct} ${closest}`;});out.push(String(new Set(kids.flatMap((kid) => kid.cells.map(key))).size));// every는 빈 배열에 참이므로 판 칸이 있는지를 따로 묻는다const careful = kids .filter((kid) => kid.cells.length > 0 && kid.cells.every((cell) => dist(cell) <= d)) .map((kid) => kid.name);out.push(careful.length ? careful.join(" ") : "-");console.log(out.join("\n"));
TypeScriptmain.ts · 40 줄
import { readFileSync } from "node:fs";interface Cell { r: number; c: number;}interface Kid { name: string; cells: Cell[];}const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, a, b, d] = lines[0].trim().split(/\s+/).map(Number);const kids: Kid[] = [];for (let i = 1; i <= n; i++) { const p = lines[i].trim().split(/\s+/); const nums = p.slice(2).map(Number); const cells: Cell[] = []; for (let j = 0; j < nums.length; j += 2) cells.push({ r: nums[j], c: nums[j + 1] }); kids.push({ name: p[0], cells });}const dist = (cell: Cell): number => Math.abs(cell.r - a) + Math.abs(cell.c - b);// Set은 객체·배열을 값이 아니라 '같은 객체인가'로 가리므로 문자열 열쇠로 바꿔 넣는다const key = (cell: Cell): string => cell.r + "," + cell.c;const out: string[] = kids.map((kid) => { const distinct = new Set(kid.cells.map(key)).size; const closest = kid.cells.length ? String(Math.min(...kid.cells.map(dist))) : "-"; // 빈 것의 Math.min은 Infinity return `${kid.name} ${distinct} ${closest}`;});out.push(String(new Set(kids.flatMap((kid) => kid.cells.map(key))).size));// every는 빈 배열에 참이므로 판 칸이 있는지를 따로 묻는다const careful: string[] = kids .filter((kid) => kid.cells.length > 0 && kid.cells.every((cell) => dist(cell) <= d)) .map((kid) => kid.name);out.push(careful.length ? careful.join(" ") : "-");console.log(out.join("\n"));
JavaMain.java · 46 줄
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.OptionalInt;import java.util.stream.Collectors;public class Main { // record는 필드 값으로 equals·hashCode를 만들어 준다: distinct()가 값으로 가린다 record Cell(int r, int c) {} record Kid(String name, List<Cell> cells) {} 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]), a = Integer.parseInt(first[1]); int b = Integer.parseInt(first[2]), d = Integer.parseInt(first[3]); List<Kid> kids = new ArrayList<>(); for (int i = 0; i < n; i++) { String[] p = in.readLine().trim().split(" "); List<Cell> cells = new ArrayList<>(); for (int j = 2; j < p.length; j += 2) cells.add(new Cell(Integer.parseInt(p[j]), Integer.parseInt(p[j + 1]))); kids.add(new Kid(p[0], cells)); } StringBuilder out = new StringBuilder(); for (Kid kid : kids) { long distinct = kid.cells().stream().distinct().count(); // 빈 스트림의 min은 빈 OptionalInt다 OptionalInt closest = kid.cells().stream().mapToInt(c -> Math.abs(c.r() - a) + Math.abs(c.c() - b)).min(); out.append(kid.name()).append(' ').append(distinct).append(' ') .append(closest.isPresent() ? String.valueOf(closest.getAsInt()) : "-").append('\n'); } out.append(kids.stream().flatMap(kid -> kid.cells().stream()).distinct().count()).append('\n'); // allMatch는 빈 스트림에 참이므로 판 칸이 있는지를 따로 묻는다 String careful = kids.stream() .filter(kid -> !kid.cells().isEmpty() && kid.cells().stream().allMatch(c -> Math.abs(c.r() - a) + Math.abs(c.c() - b) <= d)) .map(Kid::name) .collect(Collectors.joining(" ")); out.append(careful.isEmpty() ? "-" : careful).append('\n'); System.out.print(out); }}
C#Main.cs · 43 줄
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ static void Main() { var lines = Console.In.ReadToEnd().Split('\n'); var first = lines[0].Trim().Split(' ').Select(int.Parse).ToArray(); int n = first[0], a = first[1], b = first[2], d = first[3]; // 칸은 값 튜플 (R, C): 값이 같으면 같은 것으로 친다 var kids = new List<(string Name, List<(int R, int C)> Cells)>(); for (int i = 1; i <= n; i++) { var p = lines[i].Trim().Split(' '); var nums = p.Skip(2).Select(int.Parse).ToArray(); var cells = Enumerable.Range(0, nums.Length / 2).Select(j => (R: nums[2 * j], C: nums[2 * j + 1])).ToList(); kids.Add((p[0], cells)); } Func<(int R, int C), int> dist = cell => Math.Abs(cell.R - a) + Math.Abs(cell.C - b); var sb = new StringBuilder(); foreach (var kid in kids) { int distinct = kid.Cells.Distinct().Count(); // 빈 것의 Min()은 InvalidOperationException string closest = kid.Cells.Any() ? kid.Cells.Min(dist).ToString() : "-"; sb.Append($"{kid.Name} {distinct} {closest}\n"); } sb.Append(kids.SelectMany(kid => kid.Cells).Distinct().Count()).Append('\n'); // All은 빈 것에 참이므로 판 칸이 있는지를 따로 묻는다 var careful = kids.Where(kid => kid.Cells.Any() && kid.Cells.All(cell => dist(cell) <= d)) .Select(kid => kid.Name) .ToList(); sb.Append(careful.Count > 0 ? string.Join(" ", careful) : "-").Append('\n'); Console.Write(sb); }}
C++main.cpp · 55 줄
#include <algorithm>#include <cstdlib>#include <iostream>#include <ranges>#include <set>#include <string>#include <utility>#include <vector>using Cell = std::pair<int, int>; // (행, 열): pair는 값으로 견준다struct Kid { std::string name; std::vector<Cell> cells;};int main() { int n, a, b, d; std::cin >> n >> a >> b >> d; std::vector<Kid> kids(n); for (Kid& kid : kids) { int k; std::cin >> kid.name >> k; kid.cells.resize(k); for (Cell& cell : kid.cells) std::cin >> cell.first >> cell.second; } auto dist = [&](const Cell& cell) { return std::abs(cell.first - a) + std::abs(cell.second - b); }; for (const Kid& kid : kids) { // set에 넣으면 같은 칸은 하나만 남는다 std::set<Cell> distinct(kid.cells.begin(), kid.cells.end()); std::cout << kid.name << ' ' << distinct.size() << ' '; // 빈 범위에는 ranges::min을 쓸 수 없다 if (kid.cells.empty()) std::cout << "-\n"; else std::cout << std::ranges::min(kid.cells | std::views::transform(dist)) << '\n'; } // 아이마다의 칸 목록을 하나로 이어 붙인다 std::set<Cell> all; for (const Cell& cell : kids | std::views::transform(&Kid::cells) | std::views::join) all.insert(cell); std::cout << all.size() << '\n'; // all_of는 빈 범위에 참이므로 판 칸이 있는지를 따로 묻는다 auto careful = kids | std::views::filter([&](const Kid& kid) { return !kid.cells.empty() && std::ranges::all_of(kid.cells, [&](const Cell& cell) { return dist(cell) <= d; }); }); bool any = false; for (const Kid& kid : careful) { std::cout << (any ? " " : "") << kid.name; any = true; } std::cout << (any ? "\n" : "-\n");}