A table has n rows and c columns. Rows are numbered 1 to n in input order.
Each column has a kind. N is a column of integers and S is a column of strings.
A cell written ? is an empty cell. ? can appear in a column of either kind.
k sort keys are given. A key is a sign followed by a column number, like +2 or -3. + means ascending (smallest first) and - means descending (largest first).
Two rows are compared by the column of the first key, then, if equal, by the column of the second key, and so on in order.
Integers are compared by value.
Strings are compared by character code. That is, at the first position where they differ the smaller code is smaller (digits < uppercase < lowercase), and if one string is a prefix of the other, the shorter one is smaller.
An empty cell always comes after every non-empty cell, whether the key is ascending or descending. Two empty cells are equal.
Rows that are equal on every key keep their input order.
Sort the table and print the row numbers in sorted order.
Input
The first line has n, c, k. The second line has the c column kinds (N or S), and the third line has the k keys. Each of the next n lines has the c cells of a row (a value or ?). Values on a line are separated by single spaces. 1 ≤ n ≤ 10,000, 1 ≤ k ≤ c ≤ 6. Key column numbers are between 1 and c and all different. Integer cells are between −2,000,000,000 and 2,000,000,000. String cells are 1 to 8 characters of English uppercase letters, lowercase letters and digits
Output
Print the n row numbers in sorted order on one line, separated by single spaces
Example 1 · stdin
7 3 2
S N S
-2 +1
kim 30 x
Lee ? y
lee 30 z
Zed 30 w
Kim 25 d
park 41 e
kim 30 q
stdout
6 4 1 7 3 5 2
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
The keys arrive as input, so the comparison has to be assembled at run time. One function that walks the keys and checks 'empty? → different? → flip direction?' is enough. Example: column 2 descending gives 41 (row 6), the four rows with 30, 25 (row 5), then the empty cell (row 2); the 30s go by column 1 ascending, Zed < kim < lee (uppercase before lowercase), and rows 1 and 7 are both kim 30, so they keep input order. Trap one: making descending by 'multiplying the whole result by −1' brings empty cells to the front. Return for empty cells before flipping. Trap two: comparing numbers with a − b overflows a 32-bit int at 2,000,000,000 − (−2,000,000,000) and reverses the order. Use Integer.compare in Java, CompareTo in C#, (a > b) − (a < b) in C. Numbers in JavaScript, TypeScript and Craykon are floating point, so subtraction does not overflow in this range. Trap three: comparing a number column as strings gives "10" < "9" (in Craykon call ToNumber()). Trap four: functions that compare strings 'alphabetically' are not character-code order. JavaScript localeCompare puts apple before Zebra, and C# string.Compare/CompareTo also follow culture (language setting) rules rather than character codes. Character-code order is < in JavaScript, TypeScript, Python, C++ and Craykon, compareTo in Java, string.CompareOrdinal in C#, strcmp in C. Trap five: sorts that keep equal rows in order (stable) are Python sorted/list.sort, JavaScript/TypeScript sort (since ES2019), Java List.sort, C++ std::stable_sort and Craykon Sort(compare) (Sort given a function). C qsort, C++ std::sort and C# Array.Sort/List.Sort do not promise it, so add the row number as the last key. Trap six: reading an empty cell as 0 or an empty string without marking it mixes it with a real 0. Shapes by language: Python 3's sort has no comparison-function slot, so wrap it with functools.cmp_to_key; Java builds a Comparator per key and chains them with thenComparing. A C++ comparison function answers 'is it before?' as a bool, not −1/0/1, and must not return true for equal items.
Pythonmain.py · 32 lines
import sysfrom functools import cmp_to_keylines = sys.stdin.read().split("\n")n, c, k = map(int, lines[0].split())types = lines[1].split()# 기준마다 (열 번호, 내림차순인가)keys = [(int(t[1:]) - 1, t[0] == "-") for t in lines[2].split()]rows = []for i in range(n): cells = lines[3 + i].split() # 값이 없는 칸은 None, 수 열은 int, 문자열 열은 그대로 rows.append([None if v == "?" else (int(v) if types[j] == "N" else v) for j, v in enumerate(cells)])def compare(x, y): for col, desc in keys: a, b = rows[x][col], rows[y][col] if a is None or b is None: if a is None and b is None: continue return 1 if a is None else -1 # 값이 없는 칸은 방향과 상관없이 뒤로 if a != b: r = -1 if a < b else 1 # 문자열의 < 는 글자 코드 순서다 return -r if desc else r return 0# sorted는 안정 정렬이라 모든 기준이 같으면 입력 순서가 남는다order = sorted(range(n), key=cmp_to_key(compare))print(" ".join(str(i + 1) for i in order))
JavaScriptmain.js · 32 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, c, k] = lines[0].split(" ").map(Number);const types = lines[1].trim().split(" ");// 기준마다 열 번호와 방향const keys = lines[2].trim().split(" ").map((t) => ({ col: Number(t.slice(1)) - 1, desc: t[0] === "-" }));const rows = [];for (let i = 0; i < n; i++) { const cells = lines[3 + i].trim().split(" "); // 값이 없는 칸은 null, 수 열은 수로, 문자열 열은 그대로 rows.push(cells.map((v, j) => (v === "?" ? null : types[j] === "N" ? Number(v) : v)));}function compare(x, y) { for (const { col, desc } of keys) { const a = rows[x][col]; const b = rows[y][col]; if (a === null || b === null) { if (a === null && b === null) continue; return a === null ? 1 : -1; // 값이 없는 칸은 방향과 상관없이 뒤로 } if (a !== b) { const r = a < b ? -1 : 1; // 문자열의 < 는 글자 코드 순서다(localeCompare가 아니다) return desc ? -r : r; } } return 0;}// Array.prototype.sort는 안정 정렬이라(ES2019부터) 모든 기준이 같으면 입력 순서가 남는다const order = Array.from({ length: n }, (_, i) => i).sort(compare);console.log(order.map((i) => i + 1).join(" "));
TypeScriptmain.ts · 40 lines
import { readFileSync } from "node:fs";type Cell = number | string | null;interface Key { col: number; desc: boolean;}const lines: string[] = readFileSync(0, "utf8").split("\n");const [n] = lines[0].split(" ").map(Number);const types: string[] = lines[1].trim().split(" ");// 기준마다 열 번호와 방향const keys: Key[] = lines[2].trim().split(" ").map((t) => ({ col: Number(t.slice(1)) - 1, desc: t[0] === "-" }));const rows: Cell[][] = [];for (let i = 0; i < n; i++) { const cells: string[] = lines[3 + i].trim().split(" "); // 값이 없는 칸은 null, 수 열은 수로, 문자열 열은 그대로 rows.push(cells.map((v, j): Cell => (v === "?" ? null : types[j] === "N" ? Number(v) : v)));}function compare(x: number, y: number): number { for (const { col, desc } of keys) { const a: Cell = rows[x][col]; const b: Cell = rows[y][col]; if (a === null || b === null) { if (a === null && b === null) continue; return a === null ? 1 : -1; // 값이 없는 칸은 방향과 상관없이 뒤로 } if (a !== b) { const r: number = a < b ? -1 : 1; // 문자열의 < 는 글자 코드 순서다(localeCompare가 아니다) return desc ? -r : r; } } return 0;}// Array.prototype.sort는 안정 정렬이라(ES2019부터) 모든 기준이 같으면 입력 순서가 남는다const order: number[] = Array.from({ length: n }, (_, i) => i).sort(compare);console.log(order.map((i) => i + 1).join(" "));
JavaMain.java · 52 lines
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int c = Integer.parseInt(st.nextToken()); String[] types = br.readLine().trim().split(" "); String[] keyTokens = br.readLine().trim().split(" "); boolean[][] empty = new boolean[n][c]; int[][] num = new int[n][c]; // 수 열의 값 String[][] text = new String[n][c]; // 문자열 열의 값 for (int i = 0; i < n; i++) { String[] cells = br.readLine().trim().split(" "); for (int j = 0; j < c; j++) { if (cells[j].equals("?")) empty[i][j] = true; else if (types[j].equals("N")) num[i][j] = Integer.parseInt(cells[j]); else text[i][j] = cells[j]; } } // 기준 하나마다 Comparator를 만들고 thenComparing으로 잇는다 Comparator<Integer> chain = null; for (String t : keyTokens) { final int col = Integer.parseInt(t.substring(1)) - 1; final boolean desc = t.charAt(0) == '-'; final boolean numeric = types[col].equals("N"); Comparator<Integer> one = (x, y) -> { boolean ex = empty[x][col], ey = empty[y][col]; if (ex || ey) return Boolean.compare(ex, ey); // 값이 없는 칸은 방향과 상관없이 뒤로 // 뺄셈(a - b)은 넘칠 수 있으니 Integer.compare를 쓴다. compareTo는 글자 코드 순서다 int r = numeric ? Integer.compare(num[x][col], num[y][col]) : text[x][col].compareTo(text[y][col]); return desc ? -r : r; }; chain = chain == null ? one : chain.thenComparing(one); } List<Integer> order = new ArrayList<>(); for (int i = 0; i < n; i++) order.add(i); order.sort(chain); // List.sort는 안정 정렬이라 모든 기준이 같으면 입력 순서가 남는다 StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { if (i > 0) sb.append(' '); sb.append(order.get(i) + 1); } System.out.println(sb); }}
C#Main.cs · 49 lines
using System;using System.Linq;class Program{ static void Main() { var head = Console.ReadLine()!.Split(' '); int n = int.Parse(head[0]), c = int.Parse(head[1]); var types = Console.ReadLine()!.Trim().Split(' '); var keyTokens = Console.ReadLine()!.Trim().Split(' '); var keyCol = keyTokens.Select(t => int.Parse(t.Substring(1)) - 1).ToArray(); var keyDesc = keyTokens.Select(t => t[0] == '-').ToArray(); var empty = new bool[n, c]; var num = new int[n, c]; // 수 열의 값 var text = new string[n, c]; // 문자열 열의 값 for (int i = 0; i < n; i++) { var cells = Console.ReadLine()!.Trim().Split(' '); for (int j = 0; j < c; j++) { if (cells[j] == "?") empty[i, j] = true; else if (types[j] == "N") num[i, j] = int.Parse(cells[j]); else text[i, j] = cells[j]; } } var order = Enumerable.Range(0, n).ToArray(); Array.Sort(order, (x, y) => { for (int q = 0; q < keyCol.Length; q++) { int col = keyCol[q]; bool ex = empty[x, col], ey = empty[y, col]; if (ex || ey) { if (ex && ey) continue; return ex ? 1 : -1; // 값이 없는 칸은 방향과 상관없이 뒤로 } // 뺄셈(a - b)은 넘칠 수 있으니 CompareTo를 쓴다. CompareOrdinal은 글자 코드 순서다 int r = types[col] == "N" ? num[x, col].CompareTo(num[y, col]) : string.CompareOrdinal(text[x, col], text[y, col]); if (r != 0) return keyDesc[q] ? -r : r; } return x.CompareTo(y); // Array.Sort는 안정 정렬이 아니라서 입력 순서를 마지막 기준으로 넣는다 }); Console.WriteLine(string.Join(" ", order.Select(i => i + 1))); }}
C++main.cpp · 63 lines
#include <algorithm>#include <iostream>#include <numeric>#include <string>#include <vector>using namespace std;struct Cell { bool empty = false; int num = 0; // 수 열의 값 string text; // 문자열 열의 값};int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, c, k; cin >> n >> c >> k; vector<char> types(c); for (auto &t : types) cin >> t; vector<int> keyCol(k); vector<bool> keyDesc(k); for (int q = 0; q < k; q++) { string t; cin >> t; keyDesc[q] = t[0] == '-'; keyCol[q] = stoi(t.substr(1)) - 1; } vector<vector<Cell>> rows(n, vector<Cell>(c)); for (auto &row : rows) { for (int j = 0; j < c; j++) { string v; cin >> v; if (v == "?") row[j].empty = true; else if (types[j] == 'N') row[j].num = stoi(v); else row[j].text = v; } } vector<int> order(n); iota(order.begin(), order.end(), 0); // stable_sort는 모든 기준이 같으면 입력 순서를 지킨다(sort는 지키지 않는다) // 비교 함수는 'x가 y보다 앞인가'를 bool로 답한다 stable_sort(order.begin(), order.end(), [&](int x, int y) { for (int q = 0; q < k; q++) { const Cell &a = rows[x][keyCol[q]]; const Cell &b = rows[y][keyCol[q]]; if (a.empty || b.empty) { if (a.empty && b.empty) continue; return b.empty; // 값이 없는 칸은 방향과 상관없이 뒤로 } if (types[keyCol[q]] == 'N') { if (a.num != b.num) return keyDesc[q] ? a.num > b.num : a.num < b.num; } else { if (a.text != b.text) return keyDesc[q] ? a.text > b.text : a.text < b.text; // 글자 코드 순서 } } return false; }); for (int i = 0; i < n; i++) cout << (i ? " " : "") << order[i] + 1; cout << "\n"; return 0;}
Cmain.c · 61 lines
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 10000#define MAXC 6static char types[MAXC];static int keyCol[MAXC], keyDesc[MAXC], k;static char empty[MAXN][MAXC];static int num[MAXN][MAXC]; /* 수 열의 값 */static char text[MAXN][MAXC][9]; /* 문자열 열의 값(8글자까지) */static int order[MAXN];static int compare(const void *pa, const void *pb) { int x = *(const int *)pa, y = *(const int *)pb; for (int q = 0; q < k; q++) { int col = keyCol[q]; if (empty[x][col] || empty[y][col]) { if (empty[x][col] && empty[y][col]) continue; return empty[x][col] ? 1 : -1; /* 값이 없는 칸은 방향과 상관없이 뒤로 */ } int r; if (types[col] == 'N') { /* 뺄셈(a - b)은 넘칠 수 있으니 비교 두 번으로 -1, 0, 1을 만든다 */ r = (num[x][col] > num[y][col]) - (num[x][col] < num[y][col]); } else { r = strcmp(text[x][col], text[y][col]); /* 글자 코드 순서 */ } if (r != 0) return keyDesc[q] ? -r : r; } return (x > y) - (x < y); /* qsort는 안정 정렬이 아니라서 입력 순서를 마지막 기준으로 넣는다 */}int main(void) { int n, c; char tok[16]; if (scanf("%d %d %d", &n, &c, &k) != 3) return 1; for (int j = 0; j < c; j++) { scanf("%15s", tok); types[j] = tok[0]; } for (int q = 0; q < k; q++) { scanf("%15s", tok); keyDesc[q] = tok[0] == '-'; keyCol[q] = atoi(tok + 1) - 1; } for (int i = 0; i < n; i++) { for (int j = 0; j < c; j++) { scanf("%15s", tok); if (strcmp(tok, "?") == 0) empty[i][j] = 1; else if (types[j] == 'N') num[i][j] = atoi(tok); else strcpy(text[i][j], tok); } order[i] = i; } qsort(order, n, sizeof order[0], compare); for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", order[i] + 1); printf("\n"); return 0;}
Craykonmain.cray · 78 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];c = 첫줄[1];k = 첫줄[2];types = Console.ReadLine().Split(" ");// 기준마다 열 번호와 방향keyCol = [];keyDesc = [];foreach (t in Console.ReadLine().Split(" ")){ keyCol.Add(t.Substring(1).ToNumber() - 1); keyDesc.Add(t[0] == "-");}rows = [];order = [];for (i = 0; i < n; i++){ cells = Console.ReadLine().Split(" "); for (j = 0; j < c; j++) { if (cells[j] == "?") { cells[j] = null; } else if (types[j] == "N") { cells[j] = cells[j].ToNumber(); // 수로 바꿔 두지 않으면 "10" < "9"처럼 문자열로 비교된다 } } rows.Add(cells); order.Add(i);}// 앞이 먼저면 음수, 같으면 0, 뒤가 먼저면 양수compareRows(x, y){ for (q = 0; q < k; q++) { a = rows[x][keyCol[q]]; b = rows[y][keyCol[q]]; if (a == null || b == null) { if (a == null && b == null) { continue; } if (a == null) { return 1; // 값이 없는 칸은 방향과 상관없이 뒤로 } return -1; } if (a != b) { r = 1; if (a < b) { r = -1; } if (keyDesc[q]) { return -r; } return r; } } return 0;}// 정렬(비교함수)는 안정 정렬이라 모든 기준이 같으면 입력 순서가 남는다order.Sort(compareRows);out = [];foreach (i in order){ out.Add(i + 1);}Console.WriteLine(out.Join(" "));