개발자 톡
연습문제 톡
[HSAT 7회 정기 코딩 인증평가 기출] 자동차 테스트
시간복잡도 O(NlogN)~=O(Q) : 제일 빠른 풀이 (답 주의)
- 등록일
- 2024-09-18 14:49:38
- 조회수
- 252
- 작성자
- sh2298
문제의 특성은 데이터가 너무 크다는 것이고 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번 조건을 위한, 더 빨리 풀 수 있도록 하는 힌트입니다. 서로 다름을 가정 = 각 숫자마다 index 부여 가능
따라서 저희가 찾고자 하는 median 의 index를 미리 부여해놓으면 찾을 수 있습니다.
아래는 이것을 구현한 코드이며 아래와 같은 복잡도를 가집니다.
TC : O(NlogN)~=O(Q) (NlogN이 23만 정도 됩니다)
SC : O(N)
감사합니다!
import sys input = sys.stdin.readline def solve(median): m_idx = index.get(median, None) if median == data[0] or median == data[-1] or not m_idx: return 0 return m_idx * (n-m_idx-1) if __name__ == "__main__": n, q = map(int, input().split()) data = list(map(int, input().split())) data.sort() index = {d:i for i, d in enumerate(data)} for _ in range(q): median = int(input()) print(solve(median))
#[HSAT_7회_정기_코딩_인증평가_기출]_자동차_테스트