개발자 톡

연습문제 톡 [HSAT 7회 정기 코딩 인증평가 기출] 자동차 테스트

시간복잡도 O(NlogN)~=O(Q) : 제일 빠른 풀이 (답 주의)

등록일
2024-09-18 14:49:38
조회수
252
작성자
sh2298

문제의 특성은 데이터가 너무 크다는 것이고 O(NQ)만 되도 벌써 시간초과가 뜰 것입니다.


다만 여기서 큰 힌트 2가지를 통해 시간복잡도를 선형으로 대폭 줄일 수 있습니다.



  1. 중앙값을 구할 수 있는 경우의 수만 찾으면 됨
  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회_정기_코딩_인증평가_기출]_자동차_테스트

이 카테고리의 톡 더보기