[백준] 2075번 : N번째 큰 수 (C언어 / C99)

문제

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

12	7	9	15	5
13	8	11	19	6
21	10	26	31	16
48	14	28	35	25
52	20	32	41	49

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

 

 

조건 및 입출력

- 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

- 첫째 줄에 N번째 큰 수를 출력한다.

- 시간 제한: 1초 이내 / 메모리 제한: 12MB 이내

 

 

코드 (C99)

#include <stdio.h>
#define DATA_SIZE 2250000

//전역변수 선언부
int nums[DATA_SIZE] = { 0 };

//프로토타입 선언부
void heap_sort(int nums[], int size);

main()
{
	int n, index = 0;
	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			scanf("%d", &nums[index]);
			index++;
		}
	}

	heap_sort(nums, index);

	printf("%d\n", nums[index - n]);

	return 0;
}

void heap_sort(int nums[], int size)
{
	for (int i = 1; i < size; i++)
	{
		int child = i;
		do
		{
			int root = (child - 1) / 2;
			if (nums[root] < nums[child])
			{
				int temp = nums[root];
				nums[root] = nums[child];
				nums[child] = temp;
			}
			child = root;
		} while (child != 0);
	}

	for (int i = size - 1; i >= 0; i--)
	{
		int temp = nums[0];
		nums[0] = nums[i];
		nums[i] = temp;
		int root = 0;
		int child = 1;
		do
		{
			child = 2 * root + 1;

			if (child < i - 1 && nums[child] < nums[child + 1])
				child++;
			if (child < i && nums[root] < nums[child])
			{
				temp = nums[root];
				nums[root] = nums[child];
				nums[child] = temp;
			}
			root = child;
		} while (child < i);
	}
}

 

 

---

여담

처음 문제를 봤을 때, N^2의 입력값이 주어짐을 봤을 때, 복잡도를 낮추고 가야겠다는 생각이 들었다.

N은 최대 1500, 즉 2250000 개의 입력이 주어질 것이다.

 

이를 일일이 비교하고 N번째 최댓값을 반환하기에는 시간이 너무 오래 걸릴지도 모른다는 생각이 들었다.

저번 학기 때, 자료구조를 배웠으므로 힙 정렬을 이용해서 데이터를 한 번 정렬하고 시작했다.

 

입력 데이터는 -10억 ~ 10억의 수가 주어진다는 말에 long long 형으로 데이터를 처리하려고 했다.

파이썬에서 메모리 제한에 걸린 적은 많아도 C에서 메모리 제한 걸린 적은 기억에 없었기 때문이다. 그래서 아무 의심없이 long long으로 데이터를 처리했다가 메모리 제한에 걸려버렸다.

 

지금 단순히 생각해보면, 대략 1500*1500*8byte = 18MB인데, 

이를 생각치 못했다. 그래서 급히 int형의 표현 범위를 봤더니 대략 +-21억 까지 표현이 가능했다는 사실을 알게 되었다.

 

그렇게 모든 정수 자료형을 int형으로 고치고 제출하였더니 정답 처리 되었다.

예상했던 대로 자료형을 int형으로 바꾸니 메모리도 절반 수준으로 사용되어졌다.

 

오늘의 교훈: 자료형의 표현 범위를 익혀두자.

 

---

코드가 이상하거나, 이해되지 않는 부분이 있다면 댓글 남겨주세요! + 더 좋은 풀이 방법이 있다면 알령주세요 :)