[파이썬][백준 9024][💛골드 5] (이분탐색, 투포인터)

🧞‍♂️ 난이도

💛 골드 5

🧞‍♂️ 문제

숫자 고르기

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

🧞‍♂️ 유형

이분탐색, 투포인터

🧞‍♂️ 내 풀이

이 문제의 핵심은 두 수의 합 에서 두 수 를 어떻게 효율적으로 구할것이냐..이다 내가 푼 방법은

• 일단 첫 번째 수는 for 문으로 하나씩 구하고
• 두 번째 수는 이분탐색 으로 찾는다.
• 두개를 더한다. = _sum
• abs(k - _sum) 의 최솟값을 찾고, 그 최솟값이 몇 번 나오는지 찾는다.

---

🧞‍♂️ 파이썬 풀이

import sys
input = sys.stdin.readline

def binarySearch(arr, target):
    closest, closestCount = float('inf'), 0
    for i in range(len(arr)):
        left, right = i + 1, len(arr) - 1
        while left <= right:
            mid = left + (right - left) // 2
            _sum = arr[i] + arr[mid]
            if abs(target - _sum) < closest:
                closest = abs(target - _sum)
                closestCount = 1
            elif abs(target - _sum) == closest:
                closestCount += 1
            if _sum > target:
                right = mid - 1
            else:
                left = mid + 1
    return closestCount
    
t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    nums = sorted(list(map(int, input().split())))
    print(binarySearch(nums, k))

맨 위로 이동하기

BOJ 카테고리 내 다른 글 보러가기