[백준/BOJ] 20937. 떡국 [Silver 4]

20937. 떡국

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

code

#include <stdio.h>
void QuickSort(int* arr, int start, int end)
{
	if (start >= end)
		return;
	int piv = start, left = start + 1, right = end, temp;
	while (left <= right)
	{
		while (left <= end && arr[left] <= arr[piv])
			left++;
		while (right > start && arr[right] >= arr[piv])
			right--;
		if (left > right)
		{
			temp = arr[right];
			arr[right] = arr[piv];
			arr[piv] = temp;
		}
		else
		{
			temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
	}
	QuickSort(arr, start, right - 1);
	QuickSort(arr, right + 1, end);
}
int tteok[500000] = { 0 };
int main()
{
	int N, i, cnt = 1, max = 1;
	scanf("%d", &N);
	for (i = 0; i < N; i++)
		scanf("%d", &tteok[i]);
	QuickSort(tteok, 0, N - 1);
	for (i = 1; i < N; i++)
	{
		if (tteok[i] == tteok[i - 1])
		{
			cnt++;
			if (cnt > max)
				max = cnt;
		}
		else
			cnt = 1;
	}
	printf("%d", max);
	return 0;
}

알고리즘은 정말 간단하다.
그릇탑은 이전의 그릇보다 작은것들만 쌓을 수 있기때문에 크기가 같은놈들은 탑을 쌓지 못한다.
즉, 가장 많은 크기가 같은그릇의 갯수 = 그릇 탑의 갯수가 된다.

그래서 퀵소트하고 같은것을 카운팅해서 최댓값에 넣고 최댓값을 출력했는데,
왜 인지 모르겠으나 시간초과가 난다.
아무래도 퀵소트가 백준에 걸리는것 같은데,
그렇다고 정렬을 안 하자니 for문을 2번돌아야 하는 상황이 벌어지는데, 그럼 더 오래걸릴것이다...

어떻게 푸는지는 아는데 코딩에서 막힐때가 너무답답하다ㅠㅠ

C++로 풀었다. 알고리즘은 동일하고 코드만 바꾸었다.

#include <iostream>
#include <algorithm>
using namespace std;

int tteok[500000];
int main()
{
	ios::sync_with_stdio(false);

	int N, i, cnt = 1, max = 1;
	cin >> N;

	for (i = 0; i < N; i++)
		cin >> tteok[i];

	sort(tteok, tteok + N);

	for (i = 1; i < N; i++)
	{
		if (tteok[i] == tteok[i - 1])
		{
			cnt++;
			if (cnt > max)
				max = cnt;
		}
		else
			cnt = 1;
	}

	cout << max;

	return 0;
}