백준 2428 - 표절 (자바 - 이분탐색)

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

2428번: 표절

 

* 문제 요약

세계적인 석유 재벌이 1등 상품으로 페라리를 걸고 프로그래밍 대회를 개최했다. 이 대회의 참석자는 총 N명이고 각각 솔루션 파일 1개를 제출했다. 이 솔루션 파일을 F1, F2, ... Fn 이라고 한다.

채점 결과를 발표하기 전에, 남의 것을 배낀 사람이 있는지 찾아내려고 한다. 이 대회의 주최측은 두 파일을 비교해서 너무 비슷한지 아닌지 판별하는 프로그램이 있다.

하지만, 제출한 파일의 갯수가 너무 많아서 모든 쌍을 검사한다면 2012년 지구가 멸망할 때까지도 검사를 해야할 판이다.

따라서, 파일의 크기가 너무 다른 경우에는 그러한 쌍을 검사하지 않고 넘어가기로 했다.

 

좀 더 정확하게 하기 위해서, 대회의 심판들은 두 파일이 있을 때 작은 파일의 크기가 큰 파일 크기의 90% 보다도 작을 때는 이러한 쌍은 검사하지 않고 넘어가기로 했다.

따라서 (Fi, Fj) 쌍을 검사해야 하는데, 이 때 i != j 이고 size(Fi) <= size(Fj) 이면서 size(Fi) >= 0.9 x size(Fj) 인 쌍만 검사하려고 한다.

몇 개의 쌍을 검사해야 하는지 구하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 제출한 솔루션의 갯수 N이 주어진다. 둘째 줄에는 각 솔루션 파일의 크기 size(F1), size(F2), ... size(Fn) 이 주어진다. (1 <= N <= 100,000, 1 <= size(Fi) <= 100,000,000) 솔루션 파일의 크기는 정수이다.

 

* 출력

첫째 줄에 검사해야 하는 파일의 갯수를 출력한다.

 

* 예시

 

* 해결 과정

오름차순으로 정렬된 중복이 존재하는 배열에서 현재 파일을 기준으로 바로 오른쪽에 있는 파일부터 가장 끝에 있는 파일까지를 초기 범위로 하여 이분탐색을 진행했다.

이분탐색을 통해 최초로 현재 탐색중인 파일의 90퍼센트 크기를 초과하는 파일 발견 시 해당 인덱스의 바로 왼쪽에 있는 인덱스를 반환해준 다음(최대로 비교 가능한 크기만큼의 파일 위치 인덱스), 해당 인덱스에서 부터 현재 탐색중인 파일 인덱스 간의 차이 만큼을 계산해서 비교횟수에 합산해주는 과정을 모든 파일에 대해 반복 수행해주는 방식으로 전체 비교횟수를 구했다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

    static int[] contestArray = null;

    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int count = Integer.parseInt(br.readLine());
        String[] inputArray = br.readLine().split(" ");
        contestArray = new int[count];

        for (int i = 0; i < count; i++) {
            contestArray[i] = Integer.parseInt(inputArray[i]);
        }

        Arrays.sort(contestArray);

        long comCount = 0; // 총 비교횟수

        for (int i = 0; i < contestArray.length - 1; i++) {
            int number = contestArray[i];

            if (number >= 0.9 * contestArray[i + 1]) { // 시작 지점의 바로 다음 요소부터 비교 가능한 경우
                int index = upperBound(number, i);
                comCount += (index - i);
            }
            // 시작 지점의 바로 다음 요소부터 비교 불가능한 경우 따로 로직을 수행하지 않음
        }

        bw.write(comCount + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    // 중복이 존재하는 배열에서 최초로 현재 탐색중인 파일 크기의 90퍼센트 보다 더 큰 파일의 위치를 찾는다.
    private static int upperBound(int number, int i) {
        int start = i + 1;
        int end = contestArray.length;

        while (start < end) {
            int mid = (start + end) / 2;
            if (contestArray[mid] * 0.9 <= number) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start - 1;
    }
}

 

현재 탐색중인 파일을 기준으로 오른쪽에 있는 파일들을 초기 범위로 설정해준 뒤, 중간값이 현재 탐색중인 파일 크기의 90퍼센트를 초과하느냐 그렇지 않느냐에 따라 범위를 좁혀가며 현재 탐색중인 파일과 비교가 가능한 파일들의 범위를 찾아서 그 갯수를 구해주는 방식으로 문제를 해결하였으므로 이분탐색 문제에 해당된다.