문제 링크

풀이

입력으로 들어오는 값이 중앙값이 되는 경우의 수를 구하기 위해서는 우선 자동차 연비들을 배열에 저장 후, 오름차순 혹은 내림차순으로 정렬한다.
그리고 중앙값이 되어야하는 값의 인덱스를 찾은 후에 그 값보다 작은 인덱스를 가지는 요소 개수와 그 값보다 큰 인덱스를 가지는 요소의 개수를 곱해주면 된다. 이 때, 배열 내에 중앙값이 되어야하는 요소가 없다면 0을 출력해야한다.

⏱️ 시간초과
처음에는 선형탐색으로 중앙값을 찾고 위 풀이대로 값들을 구하여 곱했지만 시간초과로 인해 틀렸다.
문제의 조건을 살펴보면 연비는 최대 50,000개가 입력될 수 있다. 그리고 최대200,000개의 입력에 대한 결과를 출력해야한다. 따라서 선형탐색으로 중앙값의 인덱스를 찾게되면 O(1,000,000,000)이므로 시간초과가 날 수 밖에 없다.

이를 해결하기 위해서 O(log(n))의 시간 복잡도를 가지는 이분탐색(binary search)을 활용해야한다.

따라서 선형 탐색을 사용하는 indexOf() 메서드가 아닌 binarySearch() 메서드를 사용하여 중앙값의 인덱스를 찾아야한다.
해당 메서드는 binarySearch(컬렉션, 찾고자하는 값)으로 사용할 수 있다. 값이 존재한다면 인덱스를 반환하고, 존재하지 않는다면 (-(insertion point) - 1)을 반환한다. insertion point란 리스트 내에 찾고자하는 값이 삽입되어야할 인덱스를 의미한다.

List<Integer> numbers = new ArrayList<>(List.of(1, 3, 5, 7, 9));

// 존재하지 않는 값 4를 검색할 경우
int index = Collections.binarySearch(numbers, 4);
System.out.println(index); // 결과: -3

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n, q;
    static List<Integer> fuels;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        q = Integer.parseInt(st.nextToken());

        fuels = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            fuels.add(Integer.parseInt(st.nextToken()));
        }

        fuels.sort(null);
        for(int i = 0; i < q; i++){
            int m = Integer.parseInt(br.readLine());
            System.out.println(func(m));
        }
        
    }

    public static int func(int m){
        int index = Collections.binarySearch(fuels, m);
        if(index >= 0){
            return index * ((n - 1) - index);
        } else return 0;
    }
}