상자 n개가 1번부터 n번까지 있고, i번 상자의 무게는 w_i다.
순위표는 n칸이고, 칸마다 상자 하나를 가리킨다. 처음에는 r번째 칸이 r번 상자를 가리킨다.
명령은 다섯 가지다.
- sort: 순위표를 다시 세운다. 무거운 상자를 가리키는 칸이 앞에 오고, 무게가 같으면 번호가 작은 상자가 앞에 온다.
- add r v: 순위표 r번째 칸이 가리키는 상자의 무게에 v를 더한다. 순위표는 다시 세우지 않는다.
- swap i j: i번 상자와 j번 상자의 무게를 맞바꾼다. 순위표의 칸들은 계속 같은 번호의 상자를 가리킨다. i와 j는 같을 수 있고, 그때는 아무것도 바뀌지 않는다.
- who r: 순위표 r번째 칸이 가리키는 상자의 번호를 한 줄에 출력한다.
- show: 순위표 첫 칸부터 차례로, 칸이 가리키는 상자의 무게 n개를 빈칸 하나씩 띄워 한 줄에 출력한다.
첫 줄에 n과 q, 둘째 줄에 w_1부터 w_n까지, 다음 q줄에 명령이 하나씩 주어진다.
무게는 배열 int w[n]에 두고, 순위표는 그 칸들을 가리키는 포인터 배열 int *rank[n]으로 만들어 보자.
sort는 무게를 옮기지 말고 qsort(C++는 std::sort)로 포인터들만 늘어놓는다.
무게가 같을 때는 두 포인터 자체를 비교하고, who는 포인터 빼기 rank[r - 1] - w로 번호를 구해 보자.
swap은 두 칸의 주소를 받는 함수 void swap_weight(int *a, int *b)로 만들어 보자.
입력
1 ≤ n ≤ 1,000, 1 ≤ q ≤ 2,000, 1 ≤ r, i, j ≤ n. 무게와 v는 정수이고, 처음에도 add를 한 뒤에도 무게는 언제나 -2,000,000,000 이상 2,000,000,000 이하다(|v|도 이 범위 안). show가 출력하는 수는 모두 합쳐 15,000개 이하다. who나 show는 한 번 이상 나온다.
출력
who와 show마다 한 줄
예시 1 · stdin
4 10
5 -2 5 7
sort
show
who 2
add 4 10
swap 1 2
show
sort
show
who 3
swap 3 3
stdout
7 5 5 -2
1
7 8 5 5
8 7 5 5
2
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 2개 언어 풀이
이 문제는 C·C++만 받아요. 주소를 값으로 담는 포인터, 포인터끼리 빼서 몇 칸 떨어졌는지 구하기, 주소의 크기 비교는 두 언어에만 있어요. Python·JavaScript·TypeScript·Java·C#·크레이콘에서는 순위표에 상자 번호(자리 번호)를 담고 w[rank[r]]로 찾아가는 것이 같은 일이에요(C#의 진짜 포인터는 unsafe 안에서만 써요). C의 qsort는 늘어놓을 칸의 주소를 const void *로 비교 함수에 넘겨요. 칸에 든 것이 int *이니 *(int *const *)pa로 한 번 풀어야 포인터가 나오고, 한 번 더 풀어야(*a) 무게가 나와요. C++ std::sort는 비교 함수가 const int * 두 개를 바로 받아요. 같은 배열 안을 가리키는 두 포인터는 <로 비교할 수 있고(주소가 작으면 번호도 작아요), 빼면 그 사이 칸 수가 나와요(rank[r - 1] - w + 1이 번호). 함정 다섯: ① 비교 함수에서 *(const int *)pa처럼 한 번만 풀면 무게가 아니라 포인터 값의 일부를 비교해서 순서가 엉망이에요. ② return *b - *a;는 20억 - (-20억)처럼 차이가 int 범위(약 21억)를 넘으면 부호가 뒤집혀요. 크기를 비교해 -1·1을 돌려주세요. ③ 임시 변수 없이 *a ^= *b; *b ^= *a; *a ^= *b;로 바꾸면 a와 b가 같은 칸일 때(swap 3 3) 무게가 0이 돼요. 포인터 두 개가 같은 곳을 가리킬 수 있다는 것(별칭)을 늘 생각하세요. ④ 순위표에 포인터 대신 무게를 복사해 두면 add는 복사본만 바꾸고 swap은 순위표에 보이지 않아요. ⑤ 같은 무게를 번호로 가르지 않고 C++ std::stable_sort에 맡기면, 원래 번호 순이 아니라 add·swap을 거친 지금 순위표의 차례가 남아요.
C++main.cpp · 51 줄
#include <algorithm>#include <iostream>#include <string>#include <utility>#include <vector>// a와 b가 같은 칸을 가리켜도 맞게 바꾼다void swap_weight(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp;}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<int> w(n); // 상자의 무게. 크기를 다시 바꾸지 않으니 포인터가 계속 맞다 std::vector<int *> rank(n); // 순위표: 칸마다 w의 한 칸을 가리킨다 for (int i = 0; i < n; i++) { std::cin >> w[i]; rank[i] = &w[i]; } for (int k = 0; k < q; k++) { std::string cmd; std::cin >> cmd; if (cmd == "sort") { std::sort(rank.begin(), rank.end(), [](const int *a, const int *b) { if (*a != *b) return *a > *b; return a < b; // 무게가 같으면 주소(= 번호)가 작은 쪽이 앞 }); } else if (cmd == "add") { int r, v; std::cin >> r >> v; *rank[r - 1] += v; } else if (cmd == "swap") { int i, j; std::cin >> i >> j; swap_weight(&w[i - 1], &w[j - 1]); } else if (cmd == "who") { int r; std::cin >> r; std::cout << (rank[r - 1] - w.data()) + 1 << '\n'; } else { for (int i = 0; i < n; i++) std::cout << (i ? " " : "") << *rank[i]; std::cout << '\n'; } } return 0;}
Cmain.c · 53 줄
#include <stdio.h>#include <stdlib.h>#include <string.h>static int w[1000]; /* 상자의 무게: w[0]이 1번 상자 */static int *rank[1000]; /* 순위표: 칸마다 w의 한 칸을 가리킨다 *//* qsort는 늘어놓을 칸의 주소를 const void *로 준다. 칸에 든 것이 int *이니 진짜 타입은 int *const * */static int heavier_first(const void *pa, const void *pb) { const int *a = *(int *const *)pa; const int *b = *(int *const *)pb; if (*a != *b) return *a > *b ? -1 : 1; /* 빼기(*b - *a)는 int를 넘칠 수 있다 */ return (a > b) - (a < b); /* 같은 배열 안의 포인터는 크기를 비교할 수 있다: 주소가 작으면 번호도 작다 */}/* a와 b가 같은 칸을 가리켜도 맞게 바꾼다(임시 변수) */static void swap_weight(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp;}int main(void) { int n, q; char cmd[8]; scanf("%d %d", &n, &q); for (int i = 0; i < n; i++) { scanf("%d", &w[i]); rank[i] = &w[i]; } for (int k = 0; k < q; k++) { scanf("%7s", cmd); if (strcmp(cmd, "sort") == 0) { qsort(rank, n, sizeof rank[0], heavier_first); } else if (strcmp(cmd, "add") == 0) { int r, v; scanf("%d %d", &r, &v); *rank[r - 1] += v; /* 가리키는 상자의 무게가 바뀐다 */ } else if (strcmp(cmd, "swap") == 0) { int i, j; scanf("%d %d", &i, &j); swap_weight(&w[i - 1], &w[j - 1]); } else if (strcmp(cmd, "who") == 0) { int r; scanf("%d", &r); printf("%d\n", (int)(rank[r - 1] - w) + 1); /* 포인터 빼기 = 몇 칸 떨어져 있나 */ } else { for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", *rank[i]); printf("\n"); } } return 0;}