[백준 2428번] 표절 풀이

2428번: 표절

 

N개의 파일 F1, F2, F3, ... FN이 주어질 때, Fi <= Fj 이고 Fi >= Fj*0.9 인 두 파일쌍의 개수를 세면 된다.

가장 간단한 풀이는 이중 for문으로 두 파일을 조합을 선택하여 Fi <= Fj, Fi >= Fj*0.9 를 만족하는 (Fi, Fj) 쌍을 카운트하면 된다. 하지만 이렇게 풀게 되면 시간 복잡도는 O(N^2)으로 입력 값의 개수가 큰 경우 시간 초과를 얻게 된다.

 

다른 풀이 방법으로, 정렬과 이분탐색을 이용하는 방법이 있다.

먼저 F1... FN까지 오름차순으로 정렬한다.

예를 들어 N=9이고 175 170 157 156 156 157 172 175 190 200 140이  입력되었을 때, 이를 오름차순으로 정렬하여 저장하면 다음과 같다.

 

vector<int> v(9);
140 155 155 157 170 172 175 190 200

 

벡터 v는 오름차순으로 정렬되었으므로 140 뒤에 있는 모든 수 155, 155, 157...., 200은 140 보다 크거나 같다. 따라서 140을 Fi로 가정하였을 때, 오른쪽에 있는 수들은 무조건 Fi<= Fj를 만족하게 된다. 따라서 오른쪽에 있는 수들 중 Fi*10 >= 9*Fj 를 만족하는 수를 이분 탐색 알고리즘을 사용하여 카운트하면 된다.

 

이분 탐색 함수 BinarySearch(v, i)는 Fi=v[i]일 때, v[i+1]~v[N-1] 중 Fi*10>=Fj*9를 만족하는 최대 인덱스를 탐색한다.

 

int BinarySearch(const vector<int>& v, int i) {

    int first = i+1;
    int last = (int)v.size()-1;
    int mid;
    int re = i;

    while (first <= last) {
        mid = (first+last)/2;
        if (v[i]*10 >= v[mid]*9) {
            re = mid;
            first = mid+1;
        }
        else last = mid-1;
    }
    return re;
}

 

 Fi = v[i] 일 때,  탐색범위의 시작 위치(first)는 i+1 이고, 끝 위치(last)는 N-1 이다. 이분 탐색은 시작 위치와 끝 위치의 중앙인 mid=(first+last)/2 를 검사한다.

 

만약 v[mid]에 있는 값이 v[i]*10 < v[mid]*9 라면, mid 인덱스 뒤에 있는 값 또한 조건(v[i]*10 >= v[mid]*9)을 만족할 수 없다.

 

v[mid] <= v[mid + a]

v[i]*10 < v[mid]*9 <= v[mid+a]*9

v[i]*10 < v[mid+a]*9

 

이기 때문이다. 따라서 탐색 범위에서 mid 인덱스 이후를 제외시키고 last=mid-1 로 지정한다.

 

만약 v[mid]에 있는 값이 v[i]*10 >= v[mid]*9 를 만족한다면 mid 인덱스 앞에 있는 값 또한 해당 조건을 만족한다.

 

v[mid-a] <= v[mid],

v[i]*10 >= v[mid]*9 >= v[mid-a]*9,

v[i]*10 >= v[mid-a]*9

 

이기 때문이다.  우리는 조건을 만족하는 최댓값을 찾는 것이므로 변수 re에 현재까지 최댓값의 인덱스 mid를 저장한 뒤 탐색 범위의 시작 인덱스를 first=mid+1로 지정한다.

 

이렇게 first <= last 일 때까지 반복하여 first와 last를 이동시키면, 변수 re에는  Fi*10>=Fj*9를 만족하는 최대 인덱스가 저장되어 반환된다.

 

#include <iostream>
#include <cstdio>
#include <algorithm> 
#include <cstring>
#include <vector>
#include <cmath>
#include <tuple>
using namespace std;

int BinarySearch(const vector<int>& v, int i) {

    int first = i+1;
    int last = (int)v.size()-1;
    int mid;
    int re = i;

    while (first <= last) {
        mid = (first+last)/2;
        if (v[i]*10 >= v[mid]*9) {
            re = mid;
            first = mid+1;
        }
        else last = mid-1;
    }
    return re;
}

int main() {

    int N;
    scanf("%d", &N);

    vector<int> v(N);
    for (int i=0; i<N; i++)
        scanf("%d", &v[i]);
    
    sort(v.begin(), v.end());
    long long sum = 0;
    for (int i=0; i<N; i++) 
        sum+=BinarySearch(v, i)-i;
    printf("%lld\n", sum);
    return 0;
}