[백준 2428/자바] 표절

https://www.acmicpc.net/problem/2428

 

---

처음엔 이중 for문으로 풀었는데 아니나 다를까 시간초과 ==> 시간복잡도가 O(N^2)이기 때문

분류가 이분탐색으로 돼있길래 그렇게 풀어보려 했는데 도저히 풀이가 생각이 안 나서 구글링함..

 

풀이

1. 솔루션 파일 크기를 받아 배열에 저장
2. 해당 배열 오름차순으로 정렬
   • size(Fi) ≤ size(Fj) 만족
3. 이분탐색 함수 정의 - binarySearch(int[] arr, int i)
   1. size(Fi) ≥ 0.9 × size(Fj)를 만족하는 가장 큰 j값을 리턴
   2. 배열(arr)과 i값이 주어졌을 때 i+1번째 원소부터 배열의 마지막 원소까지 검사
   3. 이분탐색 위해 start, mid, last 구함
      • start = i + 1
      • last = arr.length - 1
      • mid = (start + last) / 2;
   4. arr[mid] 값이 조건을 만족하지 않으면 그 뒤의 원소들도 조건을 만족하지 못하므로 last = mid - 1
   5. arr[mid] 값이 조건을 만족하면 앞의 원소들도 조건을 만족하므로 start = mid + 1
      • 이때 가장 큰 j값도 mid로 업데이트 됨
   6. start 값이 last보다 커지면 j값 리턴
   7. 시간 복잡도 O(logN)
4. for문을 돌며 각 배열 원소 arr[i]마다 binarySearch 실행 - 시간복잡도 O(N)
   1. 리턴값에서 i 값을 빼면 arr[i]와 조건을 만족하는 arr[j] 한 쌍의 개수가 됨
   2. 이를 result에 더함

 

외부루프의 시간복잡도가 O(N)이고, 내부 이분탐색 메소드의 시간복잡도가 O(logN)이므로

전체 시간 복잡도는 O(NlogN)

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    /**
     * 이분탐색 알고리즘 사용
     *
     * 오름차순으로 정렬된 배열과 i값이 주어졌을 때,
     * i+1번째 원소부터 검사하여
     * size(Fi) ≥ 0.9 * size(Fj)를 만족하는 가장 큰 j값 리턴
     *
     * @param arr 오름차순으로 정렬된 배열
     * @param i 시작 인덱스
     */
    static int binarySearch(int[] arr, int i) {
        int start = i + 1;
        int last = arr.length - 1;
        int mid;
        int maxIndex = i;

        while (start <= last) {
            mid = (start + last) / 2;

            if (10 * arr[i] >= 9 * arr[mid]) {
                maxIndex = mid;
                start = mid + 1;
            } else {
                last = mid - 1;
            }
        }

        return maxIndex;
    }

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

        int N = Integer.parseInt(br.readLine());
        int[] solutions = new int[N];

        // 솔루션 파일 크기
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            solutions[i] = Integer.parseInt(st.nextToken());
        }

        // 오름차순 정렬 --> Fi ≤ Fj 만족
        Arrays.sort(solutions);

        long sum = 0;   // 조건을 만족하는 쌍의 개수
        for (int i = 0; i < N; i++) {
            // 이분탐색을 통해 조건을 만족하는 최대 인덱스(j)가 리턴된 후
            // i값을 빼면 조건을 만족하는 (Fi, Fj) 쌍의 개수가 나옴
            sum += binarySearch(solutions, i) - i;
        }

        System.out.println(sum);
    }
}

---

 

참고

https://maramarathon.tistory.com/8