행이 n개, 열이 c개인 표가 있다. 행은 입력된 차례대로 1번부터 n번까지 번호가 붙어 있다.
열마다 종류가 정해져 있다. N은 정수가 든 열이고, S는 문자열이 든 열이다.
칸에 ?가 적혀 있으면 그 칸에는 값이 없다. ?는 어느 종류의 열에도 올 수 있다.
정렬 기준이 k개 주어진다. 기준은 +2나 -3처럼 부호와 열 번호를 붙여 쓴 것이다. +는 오름차순(작은 것부터), -는 내림차순(큰 것부터)이다.
두 행은 첫째 기준의 열로 먼저 견주고, 같으면 둘째 기준의 열로 견주는 식으로 차례대로 견준다.
정수는 수의 크기로 견준다.
문자열은 글자 코드 순서로 견준다. 곧 앞에서부터 처음으로 다른 글자의 코드가 작은 쪽이 작고(숫자 < 대문자 < 소문자), 한쪽이 다른 쪽의 앞부분이면 짧은 쪽이 작다.
값이 없는 칸은 오름차순이든 내림차순이든 언제나 값이 있는 칸보다 뒤에 온다. 값이 없는 칸끼리는 같다고 본다.
모든 기준에서 같은 행들은 입력된 차례를 지킨다.
표를 정렬한 뒤, 행 번호를 정렬된 차례대로 출력하라.
입력
첫 줄에 n, c, k가 주어진다. 둘째 줄에 열 종류 c개(N 또는 S)가, 셋째 줄에 기준 k개가 주어진다. 다음 n줄에 행마다 칸 c개(값 또는 ?)가 주어진다. 한 줄의 값들은 빈칸 하나로 나뉜다. 1 ≤ n ≤ 10,000, 1 ≤ k ≤ c ≤ 6. 기준의 열 번호는 1 이상 c 이하이고 서로 다르다. 정수 칸은 −2,000,000,000 이상 2,000,000,000 이하이다. 문자열 칸은 영어 대문자·소문자·숫자로 된 1~8글자이다
출력
행 번호 n개를 정렬된 차례대로 한 줄에 빈칸 하나로 띄워 출력한다
예시 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
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
기준이 입력으로 오니 비교 함수를 실행 중에 짜야 해요. 기준을 차례로 돌며 '값이 없는가 → 값이 다른가 → 방향을 뒤집는가'를 보는 함수 하나면 돼요. 예시: 둘째 열 내림차순이라 41(6번), 30인 네 행, 25(5번), 값이 없는 칸(2번) 차례이고, 30인 행들은 첫째 열 오름차순으로 Zed < kim < lee(대문자가 소문자보다 앞), 1번과 7번은 둘 다 kim 30이라 입력 차례예요. 함정 하나: 내림차순을 '비교 결과 전체에 −1 곱하기'로 만들면 값이 없는 칸까지 앞으로 와요. 값이 없는 칸은 방향을 뒤집기 전에 따로 돌려줘요. 함정 둘: 수를 a − b로 견주면 2,000,000,000 − (−2,000,000,000)이 32비트 int를 넘어 순서가 뒤집혀요. Java는 Integer.compare, C#은 CompareTo, C는 (a > b) − (a < b)를 써요. JavaScript·TypeScript·크레이콘의 수는 실수라 이 범위에서는 뺄셈으로 견줘도 넘치지 않아요. 함정 셋: 수 열을 수로 바꾸지 않고 문자열로 견주면 "10" < "9"가 돼요(크레이콘은 수로변환()). 함정 넷: 문자열을 '사전 순'으로 견주는 함수는 글자 코드 순서가 아니에요. JavaScript localeCompare는 apple을 Zebra보다 앞에 놓고, C#의 string.Compare·CompareTo도 글자 코드가 아니라 문화권(언어 설정) 규칙을 따라요. 글자 코드 순서는 JavaScript·TypeScript·Python·C++·크레이콘의 <, Java compareTo, C# string.CompareOrdinal, C strcmp예요. 함정 다섯: 같은 행의 차례를 지켜 주는(안정) 정렬은 Python sorted·list.sort, JavaScript·TypeScript sort(ES2019부터), Java List.sort, C++ std::stable_sort, 크레이콘 정렬(비교함수)예요. C qsort, C++ std::sort, C# Array.Sort·List.Sort는 지켜 주지 않으니 행 번호를 마지막 기준으로 넣어요. 함정 여섯: 값이 없는 칸을 0이나 빈 문자열로 읽어 두고 따로 표시하지 않으면 진짜 0과 섞여요. 언어별 모양: Python 3의 sort에는 비교 함수 자리가 없어 functools.cmp_to_key로 감싸고, Java는 기준마다 Comparator를 만들어 thenComparing으로 이어요. C++의 비교 함수는 −1·0·1이 아니라 '앞인가'를 bool로 답하고, 같을 때 true를 돌려주면 안 돼요.
Pythonmain.py · 32 줄
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 줄
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 줄
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 줄
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 줄
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 줄
#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 줄
#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 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];c = 첫줄[1];k = 첫줄[2];types = 콘솔.줄읽기().나누기(" ");// 기준마다 열 번호와 방향keyCol = [];keyDesc = [];각각 (t 에서 콘솔.줄읽기().나누기(" ")){ keyCol.넣기(t.부분문자열(1).수로변환() - 1); keyDesc.넣기(t[0] == "-");}rows = [];order = [];반복 (i = 0; i < n; i++){ cells = 콘솔.줄읽기().나누기(" "); 반복 (j = 0; j < c; j++) { 만약 (cells[j] == "?") { cells[j] = 빈값; } 아니면 만약 (types[j] == "N") { cells[j] = cells[j].수로변환(); // 수로 바꿔 두지 않으면 "10" < "9"처럼 문자열로 비교된다 } } rows.넣기(cells); order.넣기(i);}// 앞이 먼저면 음수, 같으면 0, 뒤가 먼저면 양수compareRows(x, y){ 반복 (q = 0; q < k; q++) { a = rows[x][keyCol[q]]; b = rows[y][keyCol[q]]; 만약 (a == 빈값 || b == 빈값) { 만약 (a == 빈값 && b == 빈값) { 건너뛰기; } 만약 (a == 빈값) { 돌려주기 1; // 값이 없는 칸은 방향과 상관없이 뒤로 } 돌려주기 -1; } 만약 (a != b) { r = 1; 만약 (a < b) { r = -1; } 만약 (keyDesc[q]) { 돌려주기 -r; } 돌려주기 r; } } 돌려주기 0;}// 정렬(비교함수)는 안정 정렬이라 모든 기준이 같으면 입력 순서가 남는다order.정렬(compareRows);out = [];각각 (i 에서 order){ out.넣기(i + 1);}콘솔.쓰기(out.잇기(" "));