백준 18870번: 좌표 압축

문제

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

---

풀이

입력한 숫자들을 그대로 출력하는 것이 아닌 상대적인 크기를 출력하는 문제입니다.

C언어는 입력한 숫자와 순서를 구조체를, 자바는 HashMap을 이용하여 표현하였습니다.

---

코드

C언어

C언어 내장 함수인 qsort 함수를 이용하여 문제를 해결하였습니다. compare 함수는 qsort가 정렬할 때 기준을 잡아주는 역할이라고 생각하면 쉽고 이 코드에서는 입력한 숫자를 의미하는 num을 기준으로 정렬합니다. 여기서 idx는 입력한 순서, 즉 num의 인덱스를 의미합니다. 출력을 위한 정수 배열 result를 동적할당하고 구조체 배열 arr를 정렬합니다. arr는 오름차순으로 정렬돼있기 때문에 앞쪽에 있는 원소의 num이 뒤쪽에 있는 것보다 작기 때문에 바로 앞의 숫자를 의미하는 min과 다르다면 result[해당 num의 idx]에 압축된 상대적인 크기를 의미하는 cnt가 1씩 커지게 됩니다.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
typedef struct {
	int num, idx;
} point;
int compare(const void* a, const void* b) {
	point o1 = *(point*)a;
	point o2 = *(point*)b;
	if (o1.num > o2.num) return 1;
	else if (o1.num < o2.num) return -1;
	else return 0;
}
main() {
	int n;
	scanf("%d", &n);
	point* arr = (point*)malloc(sizeof(point) * n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i].num);
		arr[i].idx = i;
	}
	qsort(arr, n, sizeof(point), compare);
	int* result = (int*)malloc(sizeof(int) * n);
	int cnt = -1, min = INT_MIN;
	for (int i = 0; i < n; i++) {
		if (arr[i].num != min) {
			min = arr[i].num;
			cnt++;
		}
		result[arr[i].idx] = cnt;
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", result[i]);
	}
}

자바

HashMap을 간단하게 설명하자면 어떤 key 값에 대한 value 값을 지정하는 것입니다. 이 코드에서의 key 값은 입력받은 정수 배열 num의 원소이고 value 값은 해당 원소를 압축한 값입니다. 따라서 위의 C언어 코드와 유사한 방법으로 정렬할 정수 배열 sorted를 만들고 정렬된 순서대로 cnt를 늘려가며 HashMap에 넣고 정렬되지 않은 정수 배열 num의 순서대로 각 원소(key 값)의 value 값을 Stringbuilder에 담았다가 한꺼번에 출력합니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        HashMap<Integer, Integer> map = new HashMap<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int num[] = new int[n];
        int sorted[] = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
            sorted[i] = num[i];
        }
        Arrays.sort(sorted);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (!map.containsKey(sorted[i])) {
                map.put(sorted[i], cnt++);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(map.get(num[i])).append(" ");
        }
        System.out.println(sb);
    }
}

 

sorted 배열을 정렬할 때 java.util.Arrays 클래스의 sort 메서드를 사용했습니다. 이때 sort 메서드는 어떤 방식으로 정렬을 하는지 궁금해서 찾아봤습니다.

sort() 메서드는 DualPivotQuicksort 방식을 사용하여 정렬합니다.

DualPivotQuicksort은 Vladimir Yaroslavskiy, Jon Bentley, 그리고 Joshua Bloch가 제작한 피벗을 2개 사용하는 퀵정렬 방식을 사용한다고 합니다. 평균 O(nlog(n)), 최악의 경우 O(n^2)의 시간 복잡도를 가진다고 합니다. 또한 기존의 피벗을 1개 사용하는 퀵정렬 방식보다 빠르다고 해서 테스트를 진행해봤습니다.

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    public static void quickSort(int arr[], int left, int right) {
        int i = left, j = right, pivot = arr[(left + right) / 2], temp;
        do {
            while (arr[i] < pivot) i++;
            while (arr[j] > pivot) j--;
            if (i <= j) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        } while (i <= j);
        if (left < j) quickSort(arr, left, j);
        if (i < right) quickSort(arr, i, right);
    }

    public static void main(String[] args) throws IOException {
        HashMap<Integer, Integer> map = new HashMap<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int num[] = new int[n];
        int sorted[] = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(st.nextToken());
            sorted[i] = num[i];
        }
        quickSort(sorted, 0, n - 1);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (!map.containsKey(sorted[i])) {
                map.put(sorted[i], cnt++);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(map.get(num[i])).append(" ");
        }
        System.out.println(sb);
    }
}

위: quicksort 사용, 아래: sort 메서드 사용 코드입니다.

실제로는 sort 메서드보다 퀵정렬을 사용하는 것이 더 빠르다는 것을 알 수 있었습니다.

---

결론

이 문제를 해결하고 정리하는 과정에서 평소에는 궁금하지 않았던 java.util.Arrays 클래스의 sort 메서드에 대해 알아보고 quicksort와 비교하면서 어떤 정렬 알고리즘을 사용하는지에 따라 속도 차이가 많이 날 수도 있겠다는 생각을 하게 되었습니다.