나의, 코딩 일기

문제

스네이크버드는 뱀과 새의 모습을 닮은 귀여운 생물체입니다.

스네이크버드의 주요 먹이는 과일이며 과일 하나를 먹으면 길이가 1만큼 늘어납니다.

과일들은 지상으로부터 일정 높이를 두고 떨어져 있으며 i (1 ≤ i ≤ N) 번째 과일의 높이는 hi입니다. 

스네이크버드는 자신의 길이보다 작거나 같은 높이에 있는 과일들을 먹을 수 있습니다.

스네이크버드의 처음 길이가 L일때 과일들을 먹어 늘릴 수 있는 최대 길이를 구하세요.

조건 및 입출력

- 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다.

두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다.

- 첫 번째 줄에 스네이크버드의 최대 길이를 출력합니다.

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

코드 (C99)

#include <stdio.h>

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

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

main()
{
	int test, snake;
	scanf("%d %d", &test, &snake);

	for (int i = 0; i < test; i++)
		scanf("%d", &feeds[i]);

	heap_sort(feeds, test);

	for (int i = 0; i < test; i++)
	{
		if (snake < feeds[i])
			break;
		snake++;
	}
	printf("%d", snake);

	return 0;
}

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

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

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

여담

우선 먹이의 높이 데이터를 받는다. 그리고 초기 뱀의 길이에 대한 데이터도 받는다.

그 후 먹이의 높이를 저장할 수 있는 배열에 값을 저장하고, 배열을 정렬한다.

정렬의 방식은 어려가지가 있겠으나, 나는 힙 정렬을 선호하므로 힙 정렬을 이용하여 배열을 오름차순 정렬했다.

이후, for문을 돌면서 과일 나무보다 스네이크버드가 작으면 루프를 탈출하고, 그렇지 않으면 +1을 해준다. (먹이를 먹었으므로)

그렇게 해서 루프가 종료(탈출)되면 최종 스네이크버드의 길이를 출력하면 정답이다.