링크
https://www.acmicpc.net/problem/18870
문제
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
입력
첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.
출력
첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.
제한
- 1 ≤ N ≤ 1,000,000
- -10^9 ≤ Xi ≤ 10^9
예제 입력 1
5
2 4 -10 4 -9예제 출력 1
2 3 0 3 1예제 입력 2
6
1000 999 1000 999 1000 999예제 출력 2
1 0 1 0 1 0아이디어 스케치
- 입력한 숫자의 순서대로 순위를 출력해야 한다. 이때 순위는 값이 클 수록 숫자가 증가하며 입력된 숫자가 같은 경우에는 같은 순위를 가진다.
- 입력된 숫자를 오름차순으로 정렬한 후 처음에 입력된 숫자 순서대로 각 숫자의 순위를 출력하면 된다.
- 배열 2개를 이용하여 입력받은 후 하나는 오름차순으로 정렬하고 하나는 그대로 둔다.
- 같은 숫자는 같은 순위를 가지므로 중복을 제거하여야 한다.
코드 분할 설명
scanf("%d", &n);
arr = (int*)malloc(sizeof(int) * n);
result = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
memcpy(result, arr, sizeof(int) * n);
qsort(arr, n, sizeof(arr[0]), compare);- N을 입력받은 후 N크기만큼의 배열 2개를 동적할당하여 생성한다.
- 배열의 인자를 입력받은 후 result배열에 값을 복사하여 저장한다.
- 배열을 오름차순으로 정렬하기 위해 퀵정렬을 사용하였다.
int compare(const void* first, const void* second) {
int a = *(const int*)first;
int b = *(const int*)second;
if (a > b)
return 1; //오름차순 정렬
else if (a < b)
return -1;
else
return 0;
}- 퀵정렬에 사용되는 비교함수로 오름차순 정렬을 하도록 구현하였다.
int removeDuplicates(int arr[], int n) { //중복 제거 후 배열의 요소 갯수 리턴
if (n == 0) return 0;
int j = 0;
for (int i = 1; i < n; i++) {
if (arr[i] != arr[j]) {
j++;
arr[j] = arr[i];
}
}
return j + 1; //마지막인덱스 번호 + 1이 요소의 갯수이기 때문에 +1을 한 후 리턴
}- removeDuplicates함수는 배열과 배열 요소의 갯수를 인자로 전달받아 배열의 중복을 제거한 후 제거된 배열의 요소의 갯수를 리턴하는 함수이다.
- j가 중복을 제거했을 때의 마지막 인덱스를 가리킨다. 배열 요소의 갯수는 마지막 인덱스 번호 + 1 이므로 j + 1을 리턴한다.
for (int i = 0; i < rn; i++) {
int index = binarySearch(arr, n, result[i]); //이진 검색 사용
if (index != -1)
result[i] = index;
}- 이진 검색 알고리즘을 이용하여 입력한 숫자의 순서대로 그 숫자의 크기 순위를 result배열에 저장한다.
- 오름차순 정렬 후 중복이 제거 되었기 때문에 숫자가 커질수록 큰 인덱스 값을 가지며 이 인덱스 값이 순위이다.
int binarySearch(int arr[], int n, int key) { //이진검색 알고리즘
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}- 이진검색 알고리즘이다. 다른건 없고 그냥 일반적인 이진검색이다.
전체 코드
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare(const void* first, const void* second) {
int a = *(const int*)first;
int b = *(const int*)second;
if (a > b)
return 1; //오름차순 정렬
else if (a < b)
return -1;
else
return 0;
}
int binarySearch(int arr[], int n, int key) { //이진검색 알고리즘
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid;
else if (arr[mid] < key)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
int removeDuplicates(int arr[], int n) { //중복 제거 후 배열의 요소 갯수 리턴
if (n == 0) return 0;
int j = 0;
for (int i = 1; i < n; i++) {
if (arr[i] != arr[j]) { //
j++;
arr[j] = arr[i];
}
}
return j + 1; //마지막인덱스 번호 + 1이 요소의 갯수이기 때문에 +1을 한 후 리턴
}
int main() {
int n;
int* arr;
int* result;
int rn;
scanf("%d", &n);
arr = (int*)malloc(sizeof(int) * n);
result = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
memcpy(result, arr, sizeof(int) * n);
rn = n;
qsort(arr, n, sizeof(arr[0]), compare);
n = removeDuplicates(arr, n); //중복 제거 후 배열의 요소 갯수를 저장
for (int i = 0; i < rn; i++) {
int index = binarySearch(arr, n, result[i]); //이진 검색 사용
if (index != -1)
result[i] = index;
}
for (int i = 0; i < rn; i++)
printf("%d ", result[i]);
free(arr);
free(result);
return 0;
}제출 결과
IT Velog