[Softeer](LV 3) 자동차 테스트

문제 링크

LV 3: 자동차 테스트

구현 방식

• 중앙값을 구하는 방법은, 예를 들어 연료 배열이 [5, 2, 3, 1, 6]라고 치면
  • 일단 오름차순 sort -> [1, 2, 3, 5, 6]
  • 왼쪽 끝과 오른쪽 끝, 즉 1과 6은 중앙값이 될 순 없다
  • 3이 중앙값이 될 수 있는 경우는, 3의 (왼쪽의 두 개의 수) * (오른쪽의 두 개의 수)를 곱해준 만큼의 가짓수가 존재한다 -> 2*2
• 시간 복잡도를 고려하여 hash table 자료형을 이용해주었다

코드

import sys

N, Q = map(int, sys.stdin.readline().split())
FE = list(map(int, sys.stdin.readline().split())); FE.sort()
FE_dict = dict(); FE_set = set(FE) #hash table 이용
for i in range(N): FE_dict[FE[i]] = i 

for q in range(Q):
    target = int(sys.stdin.readline())
    if target not in FE_set: print(0); continue
    target_idx = FE_dict[target]
    if target_idx == 0 or target_idx == N-1: print(0)
    else:
        left = target_idx; right = N-target_idx-1
        print(left * right)