7810

 

static int list[1000001]; //길이가 1,000,001 인 배열

static int __solution(int N, int max, int min)
{
	if (N < min)
		return N;

	int ret = 0, priv_ret = -1, acc = 0;
	for (int i = min; i <= max; i++)
	{
		if (!list[i])
			continue;

		ret = i;
		int cnt = N - acc;

		if (cnt < ret) //선택한 값이 합당하지 않을 때,
		{
			if (priv_ret < 0)
				ret = cnt;
			else if (cnt > priv_ret)
				ret = cnt;
			else
				ret = priv_ret;
			break;
		}

		acc += list[ret];
		priv_ret = ret;
	}

	return ret;
}

static int solution(void)
{
	int N, n, max = -1, min = 1000001;
	cin >> N;

	memset(list, 0, sizeof(int) * 1000001);
	for (int i = 1; i <= N; i++)
	{
		scanf("%d", &n);
		//cin >> n;
		list[n] += 1;

		if (n > max)
			max = n;
		if (n < min)
			min = n;
	}

	return __solution(N, max, min);
}

일단 입력받을 값의 범위가 백만이내라면 길이가 백만정도 되는 배열을 전역변수 형태로 두어서 테이블 처럼 사용하는 것이 나쁘지 않다는 것과,

입력받을 데이터가 일만단위 이상이라면 scanf를 사용할 것, 출력도 마찬가지로 printf 사용할 것.

실제로 cin 에서는 517ms, scanf 에서는 241ms가 걸렸음.

 

첫번째 if 문은 아래의 경우에 적합하다.

6 6 6 7 7 에서 총 원소 개수는 5개이다. 그러나 최소값은 6이 되고, 6이상의 값은 조건에 절대로 부합 하지 않게 된다.

그래서 전체 개수가 바로 답이 되는 것이다.

 

다음은 1 1 1 5 6 에 대해서 살펴보겠다.

현재 최소값인 1이 값의 후보가 되는지 살펴보면 1 이상인 개수가 5개로 1 이상이므로 참이된다.

이제 5에 대해서 살펴보겠다. 5이상인 개수는 2개이고 2 < 5 이므로 값이 될 수 없다.

그렇다면 1초과 5미만인 값 중 주어진 조건에 합당하는 최대값이 존재하게 된다. 앞선 경우에서 1을 제외하면 가능한 값의 개수는 2개이다 그래서 2가 최대가 되고 이에 해당하는 조건이 2번째 else if 이다.

 

마지막으로 1 1 1 2 10 에 대해서 살펴보면,

1은 되고, 2도 된다. 그러나 10에 대해서는 될 수 없다. 10에서 될 수 있는 개수는 1이고, 이전 결과는 2이므로 2가 답이 된다. 이것이 3번째 else 이다.