[Python] 소프티어 LV.3_자동차 테스트

소프티어 LV.3_자동차 테스트

import sys

# n대의 자동차 연비. q개의 질의-임의로 3대 자동차 골라 테스트. 특정 중앙값이 나오는 서로 다른 경우의 수

input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(int, input().split())) #개수 최대 5*10^4
c = sorted(c) #오름차순

for _ in range(q):
  m = int(input()) # 이 값이 중앙값이어야한다. 이 값보다 작은 값 * 이 값보다 큰 값
  if m not in c:
    print("0")
  else:
    i = c.index(m)
    print(i*(len(c)-1-i))

처음에 푼 방법 => 시간초과.

import sys
from bisect import bisect_left

# n대의 자동차 연비. q개의 질의-임의로 3대 자동차 골라 테스트. 특정 중앙값이 나오는 서로 다른 경우의 수

input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(int, input().split())) #개수 최대 5*10^4
c = sorted(c) #오름차순

for _ in range(q):
  m = int(input()) # 이 값이 중앙값이어야한다. 이 값보다 작은 값 * 이 값보다 큰 값
  if m not in c:
    print("0")
  else:
    i = bisect_left(c, m)
    print(i*(n-1-i))

두번째 이진탐색 파이썬 bisect함수 이용 => 여전히 시간초과.
이유 : if m not in c:

import sys
from bisect import bisect_left

# n대의 자동차 연비. q개의 질의-임의로 3대 자동차 골라 테스트. 특정 중앙값이 나오는 서로 다른 경우의 수

input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(int, input().split())) #개수 최대 5*10^4
c = sorted(c) #오름차순

for _ in range(q):
  m = int(input()) # 이 값이 중앙값이어야한다. 이 값보다 작은 값 * 이 값보다 큰 값
  i = bisect_left(c, m)
  if i<n and m==c[i]:
    print(i*(n-1-i))
  else:
    print(0)

파이썬 이진탐색 함수는 반드시 오름차순 정렬되어있을 때 사용해야하고,
bisect_left(리스트, 값)는 값이 해당 리스트의 몇번째 인덱스에 들어갈지를 반환한다.

또는
리스트에서 찾지 말고 set에서 찾기.

import sys
from bisect import bisect_left

# n대의 자동차 연비. q개의 질의-임의로 3대 자동차 골라 테스트. 특정 중앙값이 나오는 서로 다른 경우의 수

input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(int, input().split())) #개수 최대 5*10^4
c = sorted(c) #오름차순
setC = set(c)

for _ in range(q):
  m = int(input()) # 이 값이 중앙값이어야한다. 이 값보다 작은 값 * 이 값보다 큰 값
  if m not in setC:
    print(0)
  else:
    i = bisect_left(c, m)
    print(i*(n-1-i))