[백준/BOJ] 18870번 좌표 압축 (C/C++)

백준 온라인 저지(BOJ) 18870번 좌표 압축

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

* 사용언어 : C언어, C++

 

1. 문제

수직선 위에 N개의 좌표를 오름차순 순서로 변경하여 최초 위치에 출력

 

2. 풀이

입력받은 숫자를 오름차순 정렬한 후에

정렬된 숫자의 순서(order)를 최초 입력 순서(seq)대로 출력하는 문제입니다.

그리고 숫자가 같은 경우에는 동일한 순서(order)를 출력해야 합니다.

 

정렬을 한 후에 정렬된 결과를 그대로 출력하는 문제가 아니고

최초 입력 받은 순서(seq)대로 정렬 결과를 출력해야 하기 때문에

일반적인 정렬 문제에 비해서 까다로운 편입니다.

 

입력되는 숫자의 최대 개수가 1,000,000개로 적은 편이라서

정렬한 숫자의 순서(order)를 int 배열에 넣어서 O(1)의 시간복잡도로 찾아가는 방식을 생각해봤는데,

입력되는 개별 숫자의 범위가 -10억 ~ 10억이기 때문에 메모리 초과로 불가능했습니다.

(20억 * 4byte -> 약 7.4GB)

 

메모리, 시간 조건을 만족시키면서 문제를 해결하기 위해

방법을 고민하다가 아래 2가지 방식으로 구현해보았습니다.

 

2가지 모두 정답이 되는 방법이니

아래 설명과 코드를 참고하시어 편한 쪽으로 구현해보시길 바랍니다.

정렬은 둘 다 O(nlogn)의 시간복잡도를 가지는 merge sort 를 활용했습니다.

 

1) Hash 응용

처음 생각했던대로 정렬을 한 후에 각 숫자의 정렬 순서(order)를 기록하는 방식입니다.

다만 메모리 제한이 있기 때문에 20억 짜리 int 배열이 아닌 hash table 을 만들어 기록하였습니다.

 

각 숫자와 숫자의 정렬 순서(order)를 기록하기 위해 구조체를 만들었고

해당 구조체를 활용하여 hash table 을 만들었습니다.

 

메모리 용량 제한을 피하기 위해 table 은 1,000,000 * 5 크기로 설정했고

숫자가 중복되는 경우 hash table 에 넣지 않도록 처리했습니다.

 

2) 입력 순서(seq) 기억

숫자를 입력을 받을 때 각 숫자가 입력된 순서(seq)까지 함께 기록하는 방식입니다.

(초기에 구상했던 것과는 완전히 다른 방법입니다)

 

입력 자체를 struct 로 저장하는 방식으로

정렬을 하기 전에 숫자(num)와 함께 입력 순서(seq)도 기록해둡니다.

 

이후 구조체의 num 값을 사용하여 숫자를 정렬하고,

출력용 배열(res)에 정렬된 순서(order)를 기록하게 했습니다.

출력용 배열에 값을 저장할 때는 구조체에 저장된 입력 순서(seq)를 활용합니다.

 

이하 설명은 아래 코드로 대체하겠습니다.

 

 

3. 코드

1) Hash 응용

51,898KB 628ms

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
18870_좌표 압축
51896KB	628ms
*/
#include <cstdio>

const int LM = 1000000;
const int HLM = LM * 5;
int n, org[LM], a[LM], t[LM];

struct _h {
	int key;
	int order;
} H[HLM];

int hash(int value) {
	return (value + 1000000000) % HLM;
}

void add(int value, int order) {
	int h = hash(value);
	int cnt = HLM;
	while (cnt--) {
		if (H[h].key == -1) {
			H[h].key = value;
			H[h].order = order;
			return;
		}
		h = ++h % HLM;
	}
}

int find(int value) {
	int h = hash(value);
	int cnt = HLM;
	while (cnt--) {
		if (H[h].key == value) return H[h].order;
		h = ++h % HLM;
	}
	return -1;
}

void mSort(int s, int e) {
	if (s >= e) return;

	int m = (s + e) / 2;

	mSort(s, m);
	mSort(m + 1, e);

	int i = s, j = m + 1, k = s;
	while (i <= m && j <= e) {
		if (a[i] <= a[j]) t[k++] = a[i++];
		else t[k++] = a[j++];
	}

	while (i <= m) t[k++] = a[i++];
	while (j <= e) t[k++] = a[j++];

	for (i = s; i <= e; ++i) a[i] = t[i];
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
		org[i] = a[i];
	}
	mSort(0, n - 1);

	for (int i = 0; i < HLM; ++i) H[i].key = -1;

	int insertedNum = a[0], order = 0;
	add(a[0], order++);
	for (int i = 1; i < n; ++i) {
		if (a[i] != insertedNum) {
			add(a[i], order++);
			insertedNum = a[i];
		}
	}

	for (int i = 0; i < n; ++i) printf("%d ", find(org[i]));
	return 0;
}

 

2) 입력 순서(seq) 기억

20,648KB 512ms

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
18870_좌표 압축
20648KB	512ms
*/
#include <cstdio>

const int LM = 1000000;
int n, res[LM];

struct _n {
	int num;
	int seq;
} a[LM], t[LM];

void mSort(int s, int e) {
	if (s >= e) return;

	int m = (s + e) / 2;

	mSort(s, m);
	mSort(m + 1, e);

	int i = s, j = m + 1, k = s;
	while (i <= m && j <= e) {
		if (a[i].num <= a[j].num) t[k++] = a[i++];
		else t[k++] = a[j++];
	}

	while (i <= m) t[k++] = a[i++];
	while (j <= e) t[k++] = a[j++];

	for (i = s; i <= e; ++i) a[i] = t[i];
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &a[i].num);
		a[i].seq = i;
	}
	mSort(0, n - 1);

	int order = 0;
	res[a[0].seq] = order;
	for (int i = 1; i < n; ++i) {
		if (a[i].num != a[i - 1].num) ++order;
		res[a[i].seq] = order;
	}

	for (int i = 0; i < n; ++i) printf("%d ", res[i]);
	return 0;
}