[Softeer] 자동차 테스트

문제

요약

N개의 수로 이루어진 리스트가 주어진다.

한 줄에 하나씩 값을 하나 입력할 때, 해당 값이 리스트에서 중앙값이 될 수 있는 경우의 수는?

단, 값은 세개씩만 비교한다. Ex) 1 2 3 4 5 -> 1 2 3 / 1 2 4 / ...

 

원본

https://softeer.ai/practice/6247

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

풀이

오랜만에 온전히 내힘으로 푼듯한 코드

처음 풀이 방법 생각부터 틀린 부분 찾는 것까지 순조로웠다.

이진탐색은 이제 어디가서 이해했다고 말할 수 있겠다 ㅠㅜ 감격스러웡

 

풀이 아이디어

이진 탐색으로 값이 있는지 찾으면 해당 인덱스는 앞에 있는 값의 개수이고,

n-1에서 인덱스를 뺀수는 뒤에 있는 값의 개수니까 곱하면 되겠다.

여기서 한번 실수 했던 게, 값이 없을 때 마지막에 0을 리턴해주는 것이 아니라

처음에 값 not in lst 로 했다가 시간초과가 발생했다. 마지막까지 주의할것!

import sys
input = sys.stdin.readline

n, q = map(int, input().split())
lst = sorted(list(map(int, input().split())))

def binary_search(i):
    lw, up = 0, n-1
    
    while lw <= up:
        mid = (lw+up)//2
        if lst[mid] < i:
            lw = mid + 1
        elif lst[mid] > i:
            up = mid - 1
        else:
            return mid
    return 0
    
for _ in range(q):
    i = int(input())
    a = binary_search(i)
    print(a*(n-1-a))