시간복잡도 O(NlogN)~=O(Q) : 제일 빠른 풀이 (답 주의)
문제의 특성은 데이터가 너무 크다는 것이고 O(NQ)만 되도 벌써 시간초과가 뜰 것입니다. 다만 여기서 큰 힌트 2가지를 통해 시간복잡도를 선형으로 대폭 줄일 수 있습니다. 중앙값을 구할 수 있는 경우의 수만 찾으면 됨 주어지는 자동차의 연비는 서로 다름을 가정해도 좋습니다. 1번 조건은 말 그대로입니다. 중앙값이란 [1,2,3,5,8] 데이터에서도 3 [1,2,3,100,288] 데이터에서도 3입니다. 쉽게 설명하자면 인덱스만 알면 나머지 데이터가 어떻게 생겼든 상관이 없습니다. 저희는 3이 될 수 있는 조합만 찾으면 되는데 3대만 뽑는다는 건 어떻게 뽑아도 [(O), M, (O)] 가 되게끔만 해주는 "경우의 수"만 찾으면 됩니다. 그렇다면 정렬을 해놓고 (median 이전에 나오는 숫자의 개수 x 이후에 나오는 숫자의 개수) 로 그 조합을 찾을 수 잇습니다. 2번 조건은 1번 조건을 위한, 더 빨리 풀 수 있도록 하는 힌트입니다. 서로 다름을 가정 = 각 숫자마다 inde...
- 연습문제 톡
- 날짜
- 2024-09-18 14:49:38
- 작성자
- sh2298
- 댓글
- 0
#[HSAT_7회_정기_코딩_인증평가_기출]_자동차_테스트