[소프티어] [HSAT 7회 정기 코딩 인증평가 기출] 자동차 테스트(JAVA)

문제

https://softeer.ai/practice/6247

---

풀이(12분)

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

public class Main {

    static int[] efficiency;
    static int n;
    static Set<Integer> efficiencySet = new HashSet<>();

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

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

        Arrays.sort(efficiency);

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < q; i++){
            int targetNum = Integer.parseInt(br.readLine());
            int idx = binarySearch(targetNum);
            if(idx == 0 || idx == n-1){
                sb.append("0").append("\n");
                continue;
            }
            sb.append(idx * (n-1-idx)).append("\n");
        }

        System.out.println(sb);

    }

    static int binarySearch(int targetNum){
        if(!efficiencySet.contains(targetNum)){
            return 0;
        }
        int start = 0;
        int end = n-1;
        int mid;
        while(start <= end){
            mid = (start + end) / 2;
            if(efficiency[mid] > targetNum){
                end = mid - 1;
                continue;
            }
            if(efficiency[mid] < targetNum){
                start = mid + 1;
                continue;
            }
            if(efficiency[mid] == targetNum){
                return mid;
            }
        }
        return start;
    }

}

---

문제 풀이 전략

 

평균값이 아닌 중앙값을 찾는 것이란 걸 눈치채면 이분탐색으로 쉽게 접근할 수 있는 문제이다.

[도구정리] Binary Search(이분탐색/이진탐색)

 

중앙값의 인덱스를 찾아준 뒤 양쪽으로 선택할 수 있는 1개씩의 경우의 수를 곱해주면 된다.

 

또한, 연비의 중앙값에 포함되지 않는다는 것은 인덱스의 시작과 끝이거나 집합에 들어있지 않은 경우라는 것을 위하여 집합 자료구조도 사용해 주었다.