[softeer] [HSAT 7회 정기 코딩 인증평가 기출] 자동차 테스트 Java

문제사항

중앙값을 찾는 문제로 문제 로직 자체는 쉽지만 시간초과를 해결하기위해 시간을 오래 썼다.
1. 정렬을 한다.
2. 주어진 q가 존재하면 q를 기준으로 왼쪽의 개수 * 오른쪽의 개수 연산을 시행하면 경우의 수가 나온다.

문제는 여기서 q가 존재하는지 찾고 존재한다면 index가 몇번인지 찾아야 풀 수 있다는 것!

시도

처음에는 ArrayList로 배열을 받아 contains로 존재를 확인하고 indexOf로 index를 찾으려고 했다. -> 시간 초과
contains빼고 indexOf로 없으면 -1이 출력되니 indexOf만 -> 시간 초과
binarySearch로 찾기 -> 통과!
중앙값 어쩌구 할때는 binarySearch!

Arrays.binarySearch와 Collections.indexOf의 시간복잡도 차이

1. binarySearch 내부 구현
   이분탐색한다. 시간복잡도는 logN

    private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                     long key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            long midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

2. indexOf 내부구현
   냅다 size만큼 for문을 돌려버린다. 시간복잡도는 N

    int indexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        if (o == null) {
            for (int i = start; i < end; i++) {
                if (es[i] == null) {
                    return i;
                }
            }
        } else {
            for (int i = start; i < end; i++) {
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }
        return -1;
    }

정답 코드

public class Main
{
    static Scanner scan = new Scanner(System.in);
    static StringBuilder sb =new StringBuilder();
    public static void main(String args [])
    {
        int n = scan.nextInt();
        int q = scan.nextInt();
        int [] arr =new int [n];
        for(int i=0;i<n;i++){
            arr[i] = scan.nextInt();
        }
        Arrays.sort(arr);
        int size = arr.length;
        for(int i=0;i<q;i++){
            int mi = scan.nextInt();
            int idx = Arrays.binarySearch(arr,mi);
            if(idx>0){
                int ans =(idx)*(size-idx-1);
                sb.append(ans+"\n");
            }else{
                sb.append(0+"\n");
            } 
        }
        System.out.print(sb);
    }
}