[소프티어 6247번] 자동차 테스트(HSAT 7회 정기 코딩 인증평가 기출)

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

import sys

input = sys.stdin.readline

# 데이터의 중앙값을 사용하여 자동차의 평균적인 연비를 파악
# n대의 자동차를 새로 만들었지만 3대의 자동차만 테스트할 수 있는 상황

# n대의 자동차의 실제 연비 값이 주어졌을 때, q개의 질의에 대해 임의로 3대의 자동차를 골라 테스트하여
# 중앙값이 mi값이 나오는 서로 다른 경우의 수

# n개의 자동차 연비는 서로 다른 값 !

n, q = map(int,input().split())

values = sorted(list(map(int,input().split())))
length = len(values)

index = 1

test_dict = dict()
test_inputs = [int(input()) for _ in range(q)]

for v in values:
    test_dict[v] = index
    index += 1

for td in test_inputs:
    if td in test_dict:
        temp = test_dict[td]
        print((temp-1)*(length-temp))
    else:
        print(0)

 

이번 문제는 n개의 자동차 연비가 주어졌을 때, q개의 각 원소가 중앙값이 되는 서로 다른 경우의 수를 구하는 문제이다.

 

해당 문제는 생각보다 쉽게 풀이되었는데, 다음과 같은 방식으로 풀이하였다.

 

1. 자동차 연비의 값들을 오름차순으로 정렬(O(NlogN))
2. 테스트 값들에 대한 정렬 순서를 부여(test_dict[v] = index)
3. (테스트 값보다 작은 원소의 개수 * 테스트 값보다 큰 원소의 개수)를 출력