Softeer 1717
https://softeer.ai/practice/info.do?idx=1&eid=1717

문제

---

생각하기

---

• 이분 탐색을 통해 타겟 값을 찾으면 되는 문제이다.

동작

            int target = Integer.parseInt(st.nextToken());
            int ret = binarySearch(0, N - 1, target);

            if (ret == -1) {
                sb.append(0);
            } else {
                sb.append(ret * (N - (ret + 1)));
            }

target을 배열에서 찾아야 한다. m의 범위가 1,000,000,000이므로 이분 탐색을 통해서 해당 값의 위치를 찾아야 한다.

정확히는 배열의 인덱스를 이분탐색해서 mid 인덱스의 위치에 해당 값이 존재하는지를 찾는 것이다.

그 전에 이분 탐색을 위해서는 정렬을 꼭 해줘야 한다.

[5, 2, 3, 1, 6] 이면, 1 이 중앙값이 될 수 있는 경우의 수는 없다

이유는 1이 배열에 존재하기는 하나. 배열의 가장 작은 값이므로

3의 경우는 4가지가 존재한다.

1 3 5
1 3 6
2 3 5
2 3 6

이렇게 이분 탐색을 통해서 해당 값이 있는지를 파악 후
mid 인덱스의 위치 기준 이전 원소 개수 * mid 인덱스의 다음 원소 개수를 곱하면 가지 수를 구할 수 있다.

ret * (N - (ret + 1))

결과

코드

---

Java

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, Q;
    private static int[] fuelEconomies;

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() throws IOException {
        StringBuilder sb = new StringBuilder();

        StringTokenizer st;
        while (Q-- > 0) {
            st = new StringTokenizer(br.readLine());

            int target = Integer.parseInt(st.nextToken());
            int ret = binarySearch(0, N - 1, target);

            if (ret == -1) {
                sb.append(0);
            } else {
                sb.append(ret * (N - (ret + 1)));
            }
            sb.append('\n');
        }

        return sb.toString();
    } // End of solve()

    private static int binarySearch(int low, int high, int target) {
        if (low > high) return -1;

        int mid = (low + high) / 2;
        if (fuelEconomies[mid] == target) {
            return mid;
        } else if (fuelEconomies[mid] < target) {
            return binarySearch(mid + 1, high, target);
        } else {
            return binarySearch(low, mid - 1, target);
        }
    } // End of binarySearhc()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        fuelEconomies = new int[N];

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

        Arrays.sort(fuelEconomies);
    } // End of input()
} // End of Main class