[Softeer] Lv3. 자동차 테스트 (Java)

1. 문제

• 문제 링크 : Lv3. 자동차 테스트
• 주제 : 이분탐색

---

2. 풀이 과정 및 정리

임의의 3개를 선택하여 중앙값 m이 나오는 서로 다른 경우의 수를 구해야한다.

→ m보다 작은 연비 1개, m보다 큰 연비 1개를 선택하는 경우의 수를 구해야한다.

 

단, 주어지는 자동차의 연비는 서로 다름을 가정해도 좋습니다.

→ 중복된 연비는 없으므로 모두 서로 다른 경우의 수를 구할 수 있다.

 

그러므로 우선 입력받은 연비 배열을 오름차순으로 정렬했다.

여기서 중앙값의 인덱스를 구해야하는데 여기서 이분탐색을 사용했다.

이분탐색으로 구한 인덱스를 기준으로 위의 그림처럼 각각 앞과 뒤의 원소의 수를 곱해 문제를 해결했다.

---

3. 코드

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

public class Main {

    static int[] car;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

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

        Arrays.sort(car); //오름차순으로 정렬하기

        for(int i = 0; i < q; i++) {
            int m = Integer.parseInt(br.readLine());
            int idx = binarySearch(m);
            if(idx == -1) { //배열에 존재하지 않을 경우
                bw.write("0\n");
            }
            else { //배열에 존재할 경우
                bw.write(idx * (n-1-idx) + "\n");
            }
        }

        bw.flush();
        bw.close();
    }
    
    //중앙값 인덱스 찾기 - 이분탐색
    static int binarySearch(int target) {
        int start = 0;
        int end = car.length-1;
        while(start <= end) {
            int mid = (start + end) / 2;
            if(car[mid] > target) {
                end = mid - 1;
            }
            else if(car[mid] < target) {
                start = mid + 1;
            }
            else {
                return mid;
            }
        }
        return -1;
    }
}