2108번 - 통계학
일단 평균은 입력 받는 동시에 합을 누적시킨다음 나눠서 구했고,
입력 받은뒤에 정렬하고
중앙값은 중간 인덱스를 찾은다음 길이가 짝수일때 중앙 2개 평균을 출력하고,홀수일땐 그대로 출력하고
최빈값은 정렬된 배열은 수가 연속적으로 존재하는 특성을 이용해서 배열 전체를 조사하고 2개 이상일때는 정렬해서 2번째로 큰걸 찾고
범위는 맨 밑과 맨 위를 뺀 수를 출력했는데 이중 시간초과를 일으킨 원인은 과연 뭔가요?
현재 정렬은 O(N^2)인데
N = 5*10^5
N^2 = 2.5 * 10^11
이니 통과 불가능합니다.
댓글을 작성하려면 로그인해야 합니다.
ahrist123456 1년 전
일단 평균은 입력 받는 동시에 합을 누적시킨다음 나눠서 구했고,
입력 받은뒤에 정렬하고
중앙값은 중간 인덱스를 찾은다음 길이가 짝수일때 중앙 2개 평균을 출력하고,홀수일땐 그대로 출력하고
최빈값은 정렬된 배열은 수가 연속적으로 존재하는 특성을 이용해서 배열 전체를 조사하고 2개 이상일때는 정렬해서 2번째로 큰걸 찾고
범위는 맨 밑과 맨 위를 뺀 수를 출력했는데 이중 시간초과를 일으킨 원인은 과연 뭔가요?