이분탐색 응용력 키우기 연습1 -차이가 가장 가까운 값을 찾는 방법-

1. 문제

 

2428번: 표절 (acmicpc.net)

2428번: 표절

 

2. 풀이

 

$F_{1}, F_{2}, ... , F_{n}$이 주어질때, $F_{i} <= F_{j}$이면서, $F_{i} >= 0.9*F_{j}$인 $(F_{i}, F_{j})$의 개수를 구하는 문제

 

조건이 2개가 있는데.. 

 

사실 $F_{i} <= F_{j}$는 고려해야할 조건이 아니다..

 

이분탐색을 위해 F가 들어간 배열을 반드시 오름차순 정렬해야하기 때문

 

F가 들어간 배열을 먼저 정렬하고...

 

모든 i = 1, 2, ..., n에 대하여, $F_{i}$를 target으로 잡은 다음에 $F_{i} >= 0.9*F_{j}$을 만족하는 최대 인덱스 j를 찾는다

 

그러면 $F_{i}, F_{i+1}$, ..., $F_{i}, F_{j}$까지가 만족하는 순서쌍일테니까 i+1부터 j까지 개수를 더해나가면 되겠지

 

from sys import stdin

def binary_search(F,target,start,end):
    
    while start < end:
        
        mid = start + (end-start)//2

        if F[mid]*0.9 > target:
            
            end = mid
        
        else:
            
            start = mid + 1
    
    return end - 1

n = int(stdin.readline())

F = list(map(int,stdin.readline().split()))

F.sort()

count = 0

for i in range(n):
    
    k = binary_search(F,F[i],i+1,n)
        
    count += (k-i)

print(count)

 

 

이분탐색을 이용하면.. F[mid] * 0.9 > target(F[i])을 만족하면, mid보다 큰 지점 j에 대하여 $F_{i} < 0.9*F_{j}$이겠지

 

그러니까 end를 mid로 옮겨와야할거고

 

반대면 start를 mid + 1로 옮겨와서 더 큰 인덱스를 찾을 것이다

 

한마디로 upper bound를 구현하는 것

 

그러다보니 return값은 end - 1

 

사실 이 문제는 조건이 2가지 $F_{i} <= F_{j}$이면서, $F_{i} >= 0.9*F_{j}$인 $(F_{i}, F_{j})$의 개수를 이분탐색으로 어떻게 구할까?

 

생각하다가 고민했는데 $F_{i} <= F_{j}$ 이게 정렬하면 끝이라 쉽게 한듯??

 

 

3. 문제

 

17124번: 두 개의 배열 (acmicpc.net)

17124번: 두 개의 배열

 

 

4. 풀이

 

특정 수와 가장 가까운 값을 찾으라는 문제

 

근데 까다로운게 절댓값으로 가까운 값을 찾으라고 함

 

특정 수보다 작은쪽으로 가까운 값과 특정 수보다 큰 쪽으로 가까운 값 2가지가 존재할 것

 

그래서 1가지 binary search로는 답을 찾기가 쉽지 않다.. 방법이야 있을 수 있겠지만

 

특정 수보다 작거나 같으면서 최대인 값을 찾는 binary search와

 

특정 수보다 크거나 같으면서 최소인 값을 찾는 binary search 2가지를 구해서, 절댓값을 비교해서

 

작은 값이 해당 수와 가장 가까운 값일 것이다

 

from sys import stdin

#특정 수보다 크면서 최소인 값

def lower_binary_search(B,target,start,end):
    
    while start < end:
        
        mid = start + (end - start)//2

        if B[mid] >= target:
            
            end = mid
        
        else:
            
            start = mid + 1
    
    return end

#특정 수보다 작으면서 최대인 값
def upper_binary_search(B,target,start,end):
    
    while start < end:
        
        mid = start + (end-start)//2

        if B[mid] > target:
            
            end = mid
        
        else:
            
            start = mid + 1

    return end - 1


t = int(stdin.readline())

for _ in range(t):
    
    n,m = map(int,stdin.readline().split())

    A = list(map(int,stdin.readline().split()))
    B = list(map(int,stdin.readline().split()))

    B.sort()

    C = []

    for i in range(n):
        
        lower = lower_binary_search(B,A[i],0,m)
        
        #배열의 마지막을 넘어가는 경우
        if lower == m:
            
            lower -= 1

        upper = upper_binary_search(B,A[i],0,m)
        
        #배열의 마지막을 넘어가는 경우
        if upper == m:
            upper -= 1
            
        #두 수 중의 절댓값이 작은 값이 정답
        x = abs(A[i] - B[lower])
        y = abs(A[i] - B[upper])


        if x > y:
            
            C.append(B[upper])
        
        elif x < y:
            
            C.append(B[lower])
        
        else:
            
            if B[lower] > B[upper]:
                
                C.append(B[upper])
            
            else:
                
                C.append(B[lower])
    
    print(sum(C))

 

특정 수보다 작으면서 최대인 값은 upper bound로 찾을 수 있을거고

 

측정 수보다 크면서 최소인 값은 lower bound로 찾을 수 있을 것

 

그리고 lower bound와 upper bound가 배열의 길이를 넘어가서 index 에러가 나는 경우를 방지하기 위해

 

마지막에 lower, upper가 m이 되는 경우 -1을 해줘서 배열의 마지막을 가리키도록

 

이 문제 핵심은 특정 수와 절댓값이 가까운 값은 lower bound, upper bound 2개를 이용해서 찾을 수 있다는 점

 

이분탐색은 연습 많이해야겠다... 하면할수록 계속 헷갈리는데??