[정올/JUNGOL] 8578번 또래 (C/C++)

정보 올림피아드 8578번 또래

https://jungol.co.kr/problem/8578

또래 · Bronze I

 

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

 

1. 문제

N명(최대 20만)의 사람의 나이가 1부터 10^9 사이 자연수로 주어짐

나이 차이가 가장 작은 2명을 골라 그 둘의 나이 차이를 출력

 

2. 풀이

N명의 나이를 오름차순 혹은 내림차순으로 정렬합니다.

그리고 i를 0부터 N - 2까지 반복하면서 i번째의 값과 i + 1번째 값의 차이를 계산하고(diff)

이를 최소값과 비교하여 더 작은 경우 최소값을 갱신합니다.

반복문을 마친 뒤 최소값을 출력하면 됩니다.

 

N개의 숫자를 정렬하는 것은 시간 복잡도가 (nlogn)인 merge sort를 사용했습니다.

시도해보지는 않았으나 시간 복잡도가 O(n^2)인 삽입 정렬, 선택 정렬 등을 사용하면 TLE가 나올 것 같습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

#define ABS(X) ((X) > 0 ? (X) : (-(X)))

const int LM = 200000;
int N, arr[LM], tmp[LM];

void mergeSort(int s, int e) {
	if (s >= e) return;
	
	int m = (s + e) / 2;
	mergeSort(s, m);
	mergeSort(m + 1, e);

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

	while (i <= m) tmp[k++] = arr[i++];
	while (j <= e) tmp[k++] = arr[j++];

	for (i = s; i <= e; ++i) arr[i] = tmp[i];
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) scanf("%d ", &arr[i]);

	mergeSort(0, N - 1);
	
	int min = (1 << 30);
	for (int i = 0; i < N - 1; ++i) {
		int diff = ABS(arr[i] - arr[i + 1]);
		if (diff < min) min = diff;
	}

	printf("%d\n", min);
	return 0;
}