[백준] 2428번 표절

[백준] 2428번 표절

문제설명

2428번 문제

 

문제만 보면, 상당히 간단한 문제여서 금방 풀 수 있을 것 같았는데,,

늪에 빠져서 한참을 헤맸다ㅠㅅㅠ

 

문제풀이 방법

 

1. 두 파일을 비교하면서 i≠j이고, size(Fi) ≤ size(Fj)이면서, size(Fi) ≥ 0.9 × size(Fj) 이 조건을 만족시키는 쌍일 경우만 검사를 하면 된다. 

2. 하나씩 비교해가면서 탐색해도 되지만, n의 최대 크기가 100,000 이기 때문에, n^2 탐색을 하게 되면 시간초과가 날것이다. 

3. 그렇기 때문에 오름차순 정렬 후, 이분탐색을 사용해서 조건을 만족시키는 최대 값을 찾으면 된다. 

 

Example)

예를들어, 조건을 만족시키는 최대값의 index가 3이라고 가정해보자. 
그렇다면, 비교해야할 index 0 을 제외하고 index 1 ~ 3까지는 모두 검사를 해야함을 알 수 있다.

 

※ 내가 놓쳤던 부분
결과값은 int형이 아니다.

 

 

소스 코드

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

public class Main {

    static int N;
    static int[] arr;

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

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

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

        Arrays.sort(arr);

        long cnt = 0;
        for(int i=0; i<N-1; i++) {
            cnt += binarySearch(i) - i;
        }

        System.out.println(cnt);
    }

    public static int binarySearch(int s) {
        int left = s+1, right = N-1, middle = 0, ans = left;

        if(arr[s] * 10 < 9 * arr[s+1])
            return s;

        while (left <= right) {
            middle = (left + right) /2;

            if(arr[s] <= arr[middle] && arr[s] * 10 >= 9 * arr[middle]) {
                ans = middle;
                left = middle + 1;
            }
            else {
                right = middle - 1;
            }
        }

        return ans;
    }
}

 

문제링크

www.acmicpc.net/problem/2428

2428번: 표절