[백준/BOJ]17262. 팬덤이 넘쳐흘러 [Silver 5]

17262. 팬덤이 넘쳐흘러

문제출처 : https://www.acmicpc.net/problem/17262

code1

#include <stdio.h>
void BubbleSort(int start[],int end[],int number)
{
	int i, j, temp;
	for (i = number-1; i >0; i--)
		for (j = 0; j < i; j++)
			if (end[j] > end[j + 1])
			{
				temp = end[j];
				end[j] = end[j + 1];
				end[j + 1] = temp;
				temp = start[j];
				start[j] = start[j + 1];
				start[j + 1] = temp;
			}
}
int main()
{
	int N, i, cnt = 0;
	int s[100000] = { NULL }, e[100000] = { NULL };
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d %d", &s[i], &e[i]);
	BubbleSort(s, e, N);
	cnt = s[i - 1] - e[0];
	if (cnt < 0)
		printf("0");
	else
		printf("%d", cnt);
	return 0;
}

처음 이 문제를 접했을때 소트를 해야겠다! 라는 생각밖에 안들어서 소트를 하고, 모두 사인을 해줘야 하니까 가장 일찍 집에가는 친구에서부터 가장 늦게 도착하는 친구까지 시간 차이를 구하면 되겠다해서, 코드를 짰는데, 알고리즘은 성공이였지만, 백준에 제출하니까 시간초과가 뜨더라....
시간초과는 문제해결에 불필요한 알고리즘이 있다는 뜻인데, 생각해보니까, 하교하는 친구중 최소값(가장 일찍 집에가는친구), 등교하는 친구중 최댓값(가장 늦게 학교오는 친구)를 구할거면 배열을 만들어서 소트할 필요없이 입력받을때마다 검사해주면 된다.

그래서 작성한코드가 다음이다.

code2

#include <stdio.h>
int main()
{
	int N, i, fastest = 0, latest = 100000, s = 0, e = 0, result = 0;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
	{
		scanf("%d %d", &s, &e);
		if (fastest < s)
			fastest = s;
		if (latest > e)
			latest = e;
	}
	result = fastest - latest;
	if (result < 0)
		printf("0");
	else
		printf("%d", result);
	return 0;
}

한눈에 봐도 코드가 반절은 줄어들었다.
이런 시행착오를 통해 가장 효율적인 루트를 찾는것이 그리디알고리즘의 매력이 아닐까 싶다.