가전 매장의 비교 도우미가 상품 두 개 가운데 어느 쪽이 나은지 알려 준다.
상품은 n개이고 1번부터 n번까지 번호가 있으며, 상품마다 1번부터 k번까지 칸 k개에 수치(정수)가 적혀 있다.
수치를 재지 않은 칸에는 수 대신 x가 적혀 있다.
비교 기준 r개가 중요한 차례대로 주어진다.
기준 하나 "f d e"는 f번 칸을 본다는 뜻이다. d가 H이면 수치가 큰 쪽이 낫고, L이면 수치가 작은 쪽이 낫다. e는 허용 오차다.
같은 칸을 보는 기준은 두 번 나오지 않는다.
두 상품을 견줄 때는 첫째 기준부터 차례로 다음처럼 따진다.
두 상품 모두 그 칸이 x이면 이 기준에서는 비긴다.
한쪽만 x이면 d가 무엇이든 수치가 있는 쪽이 낫다.
둘 다 수치가 있고 두 수치의 차이(큰 수에서 작은 수를 뺀 값)가 e 이하이면 이 기준에서는 비긴다.
차이가 e보다 크면 d가 H일 때는 수치가 큰 쪽이, L일 때는 수치가 작은 쪽이 낫다.
비기면 다음 기준으로 넘어가고, 나은 쪽이 정해지면 거기서 멈춘다.
질문 q개가 주어지며, 질문 하나 "a b"는 a번 상품과 b번 상품을 견주라는 뜻이다(a와 b가 같을 수도 있다).
질문마다 한 줄에, 나은 상품의 번호와 승부를 가른 기준이 몇째 기준인지(첫째 기준이 1)를 빈칸 하나로 띄워 출력하라.
모든 기준에서 비기면 0만 출력한다.
입력
첫 줄에 n, k, r, q가 빈칸으로 나뉘어 주어진다. 다음 n줄에 1번 상품부터 차례로 칸 k개의 값(정수 또는 x)이 빈칸 하나로 나뉘어 주어진다. 다음 r줄에 기준 "f d e"가, 다음 q줄에 질문 "a b"가 한 줄에 하나씩 주어진다. 2 ≤ n ≤ 1,000, 1 ≤ k ≤ 8, 1 ≤ r ≤ k, 1 ≤ q ≤ 10,000, -2,000,000,000 ≤ 수치 ≤ 2,000,000,000, 1 ≤ f ≤ k, d는 H 또는 L, 0 ≤ e ≤ 1,000,000,000, 1 ≤ a, b ≤ n
출력
q줄. 줄마다 "나은 상품 번호, 승부를 가른 기준의 차례" 또는 0
예시 1 · stdin
4 3 3 5
300 45 x
320 48 7
300 60 7
300 44 x
2 L 5
3 H 1
1 H 0
1 2
1 3
1 4
2 3
4 2
stdout
2 2
1 1
0
2 1
2 2
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
두 값을 견준 결과는 '앞이 낫다·뒤가 낫다·비긴다' 셋이고, 여기에 '값이 없다'까지 끼어들어요. 그래서 순서가 중요해요: ① 둘 다 없나, ② 한쪽만 없나, ③ 차이가 오차 안인가, ④ 어느 쪽이 큰가. 방향은 (u > v) == high처럼 '큰 쪽이 u인가'와 '큰 쪽이 나은가'가 같은지로 한 번에 물을 수 있어요. 함정 하나: 수치는 ±20억이라 32비트 int에 들어가지만, 두 값의 차이는 40억까지 가서 넘쳐요. Java Math.abs(u - v)와 C#의 int 뺄셈은 오류 없이 돌아서 엉뚱한 작은 수가 되고(20억 − (−20억)이 −294,967,296), C·C++에서는 정의되지 않은 동작이에요. Java·C#은 long, C·C++은 long long으로 받아 빼고, C의 abs는 int용이니 llabs를 써요. Python 정수는 한계가 없고, JS·TS·크레이콘의 수는 2^53까지 정확해서 그대로 돼요. 함정 둘: '값이 없음'을 아주 작은 수로 대신하면 H 기준에서는 맞지만 L 기준(작을수록 좋다)에서는 없는 쪽이 이겨 버려요. 없음은 따로 두세요: Python None, JS·TS null(TS는 number | null이라 거르기 전에 빼면 컴파일 오류), C# long?, C++ std::optional<long long>, 크레이콘 빈값, Java·C는 있음을 적는 배열을 따로 둬요. 없음을 거르지 않고 견주면 언어마다 달라요: Python None < 5는 TypeError, Java는 Long이 null이면 NullPointerException, 크레이콘은 '빈값으로는 계산할 수 없어요'로 멈춰요. 조용히 넘어가는 쪽이 더 위험해요: JS는 null을 0으로 바꿔 견주고(null < 5는 참), C#의 long?는 한쪽이 null이면 <·>가 모두 거짓이고, C++ optional은 빈 쪽을 늘 더 작다고 해요. 함정 셋: 경계예요. 차이가 꼭 e일 때는 비기므로 <=이지 <가 아니에요. 함정 넷: JS에서 split으로 나눈 문자열을 수로 바꾸지 않으면 u - v는 수로 바뀌어 계산되지만 u > v는 글자 차례로 견줘서 "10" > "9"가 거짓이 돼요. Python은 문자열끼리 빼면 TypeError, 크레이콘도 '- 계산은 수끼리만 할 수 있어요'로 멈춰서 금방 드러나요. 함정 다섯: 출력하는 것은 기준이 보는 칸 번호 f가 아니라 그 기준이 몇째인지예요.
Pythonmain.py · 33 줄
import sysdef compare(x, y, rules): """(앞선 쪽, 가른 기준의 차례)를 돌려준다. 앞선 쪽은 x면 1, y면 -1, 끝까지 비기면 0.""" for j, (f, high, e) in enumerate(rules, 1): u, v = x[f], y[f] if u is None and v is None: # 둘 다 값이 없으면 이 기준은 비긴다 continue if u is None: # 값이 없는 쪽이 진다(방향과 상관없이) return -1, j if v is None: return 1, j if abs(u - v) <= e: # 차이가 허용 오차 이하이면 비긴다 continue return (1 if (u > v) == high else -1), j return 0, 0lines = sys.stdin.read().split("\n")n, k, r, q = map(int, lines[0].split())items = [[None if t == "x" else int(t) for t in line.split()] for line in lines[1 : 1 + n]]rules = []for line in lines[1 + n : 1 + n + r]: f, d, e = line.split() rules.append((int(f) - 1, d == "H", int(e)))out = []for line in lines[1 + n + r : 1 + n + r + q]: a, b = map(int, line.split()) side, j = compare(items[a - 1], items[b - 1], rules) out.append("0" if side == 0 else f"{a if side > 0 else b} {j}")print("\n".join(out))
JavaScriptmain.js · 31 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, k, r, q] = lines[0].split(" ").map(Number);// 값이 없는 칸은 null. Number("x")는 NaN이라 따로 가른다const items = lines.slice(1, 1 + n).map((line) => line.trim().split(" ").map((t) => (t === "x" ? null : Number(t))));const rules = lines.slice(1 + n, 1 + n + r).map((line) => { const [f, d, e] = line.trim().split(" "); return { f: Number(f) - 1, high: d === "H", e: Number(e) };});// [앞선 쪽, 가른 기준의 차례]: 앞선 쪽은 x면 1, y면 -1, 끝까지 비기면 0function compare(x, y) { for (let j = 0; j < rules.length; j++) { const { f, high, e } = rules[j]; const u = x[f]; const v = y[f]; if (u === null && v === null) continue; // 둘 다 값이 없으면 이 기준은 비긴다 if (u === null) return [-1, j + 1]; // 값이 없는 쪽이 진다(방향과 상관없이) if (v === null) return [1, j + 1]; if (Math.abs(u - v) <= e) continue; // 차이가 허용 오차 이하이면 비긴다 return [u > v === high ? 1 : -1, j + 1]; } return [0, 0];}const out = [];for (const line of lines.slice(1 + n + r, 1 + n + r + q)) { const [a, b] = line.split(" ").map(Number); const [side, j] = compare(items[a - 1], items[b - 1]); out.push(side === 0 ? "0" : `${side > 0 ? a : b} ${j}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 41 줄
import { readFileSync } from "node:fs";interface Rule { f: number; // 볼 칸(0부터) high: boolean; // 클수록 좋은가 e: number; // 허용 오차}const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, k, r, q]: number[] = lines[0].split(" ").map(Number);// 값이 없는 칸은 null. 타입이 number | null이라 null을 거르지 않고 빼면 컴파일러가 막는다const items: (number | null)[][] = lines .slice(1, 1 + n) .map((line: string) => line.trim().split(" ").map((t: string): number | null => (t === "x" ? null : Number(t))));const rules: Rule[] = lines.slice(1 + n, 1 + n + r).map((line: string): Rule => { const [f, d, e]: string[] = line.trim().split(" "); return { f: Number(f) - 1, high: d === "H", e: Number(e) };});// [앞선 쪽, 가른 기준의 차례]: 앞선 쪽은 x면 1, y면 -1, 끝까지 비기면 0function compare(x: (number | null)[], y: (number | null)[]): [number, number] { for (let j = 0; j < rules.length; j++) { const { f, high, e }: Rule = rules[j]; const u: number | null = x[f]; const v: number | null = y[f]; if (u === null && v === null) continue; // 둘 다 값이 없으면 이 기준은 비긴다 if (u === null) return [-1, j + 1]; // 값이 없는 쪽이 진다(방향과 상관없이) if (v === null) return [1, j + 1]; if (Math.abs(u - v) <= e) continue; // 차이가 허용 오차 이하이면 비긴다 return [u > v === high ? 1 : -1, j + 1]; } return [0, 0];}const out: string[] = [];for (const line of lines.slice(1 + n + r, 1 + n + r + q)) { const [a, b]: number[] = line.split(" ").map(Number); const [side, j]: [number, number] = compare(items[a - 1], items[b - 1]); out.push(side === 0 ? "0" : `${side > 0 ? a : b} ${j}`);}console.log(out.join("\n"));
JavaMain.java · 60 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int r = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); long[][] value = new long[n][k]; // 두 값의 차이가 40억까지라 long boolean[][] has = new boolean[n][k]; // 값이 있는 칸인가("x"면 false) for (int i = 0; i < n; i++) { st = new StringTokenizer(in.readLine()); for (int c = 0; c < k; c++) { String t = st.nextToken(); has[i][c] = !t.equals("x"); if (has[i][c]) value[i][c] = Long.parseLong(t); } } int[] field = new int[r]; boolean[] high = new boolean[r]; long[] tol = new long[r]; for (int j = 0; j < r; j++) { st = new StringTokenizer(in.readLine()); field[j] = Integer.parseInt(st.nextToken()) - 1; high[j] = st.nextToken().equals("H"); tol[j] = Long.parseLong(st.nextToken()); } StringBuilder sb = new StringBuilder(); for (int t = 0; t < q; t++) { st = new StringTokenizer(in.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int winner = 0; // 앞선 상품 번호(끝까지 비기면 0) int decided = 0; // 가른 기준의 차례 for (int j = 0; j < r && winner == 0; j++) { int f = field[j]; boolean hasA = has[a - 1][f], hasB = has[b - 1][f]; if (!hasA && !hasB) continue; // 둘 다 값이 없으면 이 기준은 비긴다 if (!hasA || !hasB) { // 값이 없는 쪽이 진다(방향과 상관없이) winner = hasA ? a : b; } else { long u = value[a - 1][f], v = value[b - 1][f]; if (Math.abs(u - v) <= tol[j]) continue; // 차이가 허용 오차 이하이면 비긴다 winner = (u > v) == high[j] ? a : b; } decided = j + 1; } if (winner == 0) sb.append("0\n"); else sb.append(winner).append(' ').append(decided).append('\n'); } System.out.print(sb); }}
C#Main.cs · 57 줄
using System;using System.Text;class Program{ static void Main() { string[] head = Console.ReadLine().Trim().Split(' '); int n = int.Parse(head[0]), k = int.Parse(head[1]), r = int.Parse(head[2]), q = int.Parse(head[3]); // long?는 값이 없을 수 있는 long이다("x"면 null). 두 값의 차이가 40억까지라 int로는 모자란다 var items = new long?[n][]; for (int i = 0; i < n; i++) { string[] w = Console.ReadLine().Trim().Split(' '); items[i] = new long?[k]; for (int c = 0; c < k; c++) items[i][c] = w[c] == "x" ? (long?)null : long.Parse(w[c]); } var field = new int[r]; var high = new bool[r]; var tol = new long[r]; for (int j = 0; j < r; j++) { string[] w = Console.ReadLine().Trim().Split(' '); field[j] = int.Parse(w[0]) - 1; high[j] = w[1] == "H"; tol[j] = long.Parse(w[2]); } var sb = new StringBuilder(); for (int t = 0; t < q; t++) { string[] w = Console.ReadLine().Trim().Split(' '); int a = int.Parse(w[0]), b = int.Parse(w[1]); int winner = 0; // 앞선 상품 번호(끝까지 비기면 0) int decided = 0; // 가른 기준의 차례 for (int j = 0; j < r && winner == 0; j++) { long? u = items[a - 1][field[j]], v = items[b - 1][field[j]]; if (u == null && v == null) continue; // 둘 다 값이 없으면 이 기준은 비긴다 if (u == null || v == null) { winner = u != null ? a : b; // 값이 없는 쪽이 진다(방향과 상관없이) } else { if (Math.Abs(u.Value - v.Value) <= tol[j]) continue; // 차이가 허용 오차 이하이면 비긴다 winner = (u.Value > v.Value) == high[j] ? a : b; } decided = j + 1; } if (winner == 0) sb.Append("0\n"); else sb.Append(winner).Append(' ').Append(decided).Append('\n'); } Console.Write(sb.ToString()); }}
C++main.cpp · 58 줄
#include <cstdlib>#include <iostream>#include <optional>#include <string>#include <vector>using namespace std;struct Rule { int f; // 볼 칸(0부터) bool high; // 클수록 좋은가 long long e; // 허용 오차};int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k, r, q; cin >> n >> k >> r >> q; // optional은 값이 없을 수 있는 칸이다("x"면 nullopt). 두 값의 차이가 40억까지라 long long vector<vector<optional<long long>>> items(n, vector<optional<long long>>(k)); for (auto& row : items) { for (auto& cell : row) { string token; cin >> token; if (token != "x") cell = stoll(token); } } vector<Rule> rules(r); for (Rule& rule : rules) { char dir; cin >> rule.f >> dir >> rule.e; rule.f--; rule.high = dir == 'H'; } while (q--) { int a, b; cin >> a >> b; int winner = 0; // 앞선 상품 번호(끝까지 비기면 0) int decided = 0; // 가른 기준의 차례 for (int j = 0; j < r && winner == 0; j++) { const optional<long long>& u = items[a - 1][rules[j].f]; const optional<long long>& v = items[b - 1][rules[j].f]; if (!u && !v) continue; // 둘 다 값이 없으면 이 기준은 비긴다 if (!u || !v) { // 값이 없는 쪽이 진다(방향과 상관없이) winner = u ? a : b; } else { if (llabs(*u - *v) <= rules[j].e) continue; // 차이가 허용 오차 이하이면 비긴다 winner = (*u > *v) == rules[j].high ? a : b; } decided = j + 1; } if (winner == 0) cout << "0\n"; else cout << winner << ' ' << decided << '\n'; } return 0;}
Cmain.c · 53 줄
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 1000#define MAXK 8static long long value[MAXN][MAXK]; /* 두 값의 차이가 40억까지라 long long */static int has[MAXN][MAXK]; /* 값이 있는 칸인가("x"면 0) */static int field[MAXK], high[MAXK];static long long tol[MAXK];int main(void) { int n, k, r, q; if (scanf("%d %d %d %d", &n, &k, &r, &q) != 4) return 0; for (int i = 0; i < n; i++) { for (int c = 0; c < k; c++) { char token[16]; scanf("%15s", token); has[i][c] = strcmp(token, "x") != 0; if (has[i][c]) value[i][c] = atoll(token); } } for (int j = 0; j < r; j++) { char dir[4]; scanf("%d %3s %lld", &field[j], dir, &tol[j]); field[j]--; high[j] = dir[0] == 'H'; } for (int t = 0; t < q; t++) { int a, b; scanf("%d %d", &a, &b); int winner = 0; /* 앞선 상품 번호(끝까지 비기면 0) */ int decided = 0; /* 가른 기준의 차례 */ for (int j = 0; j < r && winner == 0; j++) { int f = field[j]; int hasA = has[a - 1][f], hasB = has[b - 1][f]; if (!hasA && !hasB) continue; /* 둘 다 값이 없으면 이 기준은 비긴다 */ if (!hasA || !hasB) { /* 값이 없는 쪽이 진다(방향과 상관없이) */ winner = hasA ? a : b; } else { long long u = value[a - 1][f], v = value[b - 1][f]; if (llabs(u - v) <= tol[j]) continue; /* 차이가 허용 오차 이하이면 비긴다 */ winner = (u > v) == high[j] ? a : b; } decided = j + 1; } if (winner == 0) printf("0\n"); else printf("%d %d\n", winner, decided); } return 0;}
Craykonmain.cray · 81 줄
// [앞선 쪽, 가른 기준의 차례]: 앞선 쪽은 x면 1, y면 -1, 끝까지 비기면 0견주기(x, y, rules){ 반복 (j = 0; j < rules.개수; j++) { f = rules[j][0]; high = rules[j][1]; u = x[f]; v = y[f]; 만약 (u == 빈값 && v == 빈값) { 건너뛰기; } 만약 (u == 빈값) { 돌려주기 [-1, j + 1]; } 만약 (v == 빈값) { 돌려주기 [1, j + 1]; } 만약 (수학.절댓값(u - v) <= rules[j][2]) { 건너뛰기; } 만약 (u > v == high) { 돌려주기 [1, j + 1]; } 돌려주기 [-1, j + 1]; } 돌려주기 [0, 0];}첫줄 = 콘솔.수들읽기();n = 첫줄[0];r = 첫줄[2];q = 첫줄[3];items = [];반복 (i = 0; i < n; i++){ 칸들 = []; 각각 (t 에서 콘솔.줄읽기().나누기()) { 만약 (t == "x") { 칸들.넣기(빈값); // 값이 없는 칸. 빈값으로 빼거나 견주면 멈추므로 먼저 걸러야 한다 } 아니면 { 칸들.넣기(t.수로변환()); } } items.넣기(칸들);}rules = []; // [볼 칸(0부터), 클수록 좋은가, 허용 오차]반복 (j = 0; j < r; j++){ w = 콘솔.줄읽기().나누기(); rules.넣기([w[0].수로변환() - 1, w[1] == "H", w[2].수로변환()]);}반복 (t = 0; t < q; t++){ 쌍 = 콘솔.수들읽기(); 결과 = 견주기(items[쌍[0] - 1], items[쌍[1] - 1], rules); 만약 (결과[0] == 0) { 콘솔.쓰기(0); } 아니면 만약 (결과[0] > 0) { 콘솔.쓰기(쌍[0] + " " + 결과[1]); } 아니면 { 콘솔.쓰기(쌍[1] + " " + 결과[1]); }}