백준 2108 : 통계학

코딩테스트/백준

Mev01 2020. 9. 5. 00:43

2108번: 통계학

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

www.acmicpc.net

최빈값 같은 경우 정수의 절댓값이 4000을 넘지 않으므로 8001개의 원소를 가지는 배열을 생성

각 숫자가 나올때 +1을 해주었다.

나중에 배열을 검사하면서 제일 큰 원소를 찾고, 지금 있는 최댓값과 같은 원소가 있다면 두 번째까지만 인덱스를 저장한다.

정렬을 직접 구현하였는데 퀵소트로 구현할 경우 제출 시 46~50% 정도에서 많은 시간이 걸리는 것을 확인할 수 있다.

그래서 합병 정렬을 사용해 풀었다.