[Softeer] HSAT 7회 기출 - 자동차 테스트

문제

<배경>

자동차 제조 과정에서는 다양한 테스트를 통해 해당 자동차가 잘 만들어졌는지를 평가합니다.

이러한 평가 지표 중 하나는 자동차의 연비입니다.

자동차의 연비가 높을수록 연료 소비가 적고, 더 많은 거리를 주행할 수 있으므로 이는 자동차가 잘 만들어졌는지의 지표로 사용될 수 있습니다.

 

만약 3대의 자동차를 테스트하고, 각각의 연비를 측정한다고 가정해봅시다.

첫 번째 자동차의 연비는 9km/L, 두 번째 자동차의 연비는 15km/L, 세 번째 자동차의 연비는 20km/L이라고 합시다.

이 경우, 중앙값은 15km/L이 됩니다.

따라서 이 데이터에서는 중앙값을 이용하여 자동차의 평균적인 연비를 파악할 수 있으며, 이는 자동차 제조 과정에서 테스트의 결과를 평가하는데에 활용될 수 있습니다.

 

$n$대의 자동차를 새로 만들었지만 여건상 3대의 자동차에 대해서만 테스트가 가능한 상황입니다. $n$대의 자동차의 실제 연비 값이 주어졌을 때, $q$개의 질의에 대해 임의로 3대의 자동차를 골라 테스트하여 중앙값이 $m_i$값이 나오는 서로 다른 경우의 수를 구하는 프로그램을 작성해보세요.

 

<입력>

<출력>

$q$개의 줄에 걸쳐 3대의 자동차를 골랐을 때 연비의 중앙값이 $m_i$가 나오는 서로 다른 가짓수를 한 줄에 하나씩 출력합니다.

---

풀이

문제와 풀이 알고리즘은 모두 간단한데 시간 초과를 신경써야한다.

알고리즘은 정렬 후 해당 중앙값 보다 작은 원소의 개수와 큰 원소의 개수를 세서 곱하면 된다.

파이썬으로 풀기 때문에 시간을 아끼기 위해 여러 유용한 방법을 사용할 수 있다.

import bisect를 통해 이진탐색을 한 줄로 할 수 있다.

또 m not in mileage를 하면 시간이 오래 걸리므로 set자료형의 특징을 살려 set으로 변환 후 not in을 판단해줬다.

import bisect
n,q = map(int,input().split())
mileage = list(map(int,input().split()))
mileage.sort()
setMileage = set(mileage)

for _ in range(q):
    m = int(input())
    if m not in setMileage:
        print(0)
    else:
        idx = bisect.bisect_left(mileage,m)
        print(idx*(n - idx - 1))