사용자 도구

사이트 도구


ps:problems:boj:9024

두 수의 합

ps
링크acmicpc.net/…
출처BOJ
문제 번호9024
문제명두 수의 합
레벨골드 5
분류

정렬

시간복잡도O(t*nlogn)
인풋사이즈t<=?, n<=1,000,000
사용한 언어Python
제출기록217040KB / 2852ms
최고기록2628ms
해결날짜2021/09/20

풀이

  • 두 용액의 응용. 합이 0에 가까운 두 수를 찾는 대신, K에 가까운 두 수를 찾아야 한다.
  • 두 용액에서 설명한 두가지 방법인 투포인터와 절댓값 기준 정렬을 모두 같은 시간복잡도인 O(nlogn)으로 사용가능하다. 후자의 경우는 정렬 기준을 abs(x)가 아니라 abs(x - K/2)로 잡으면 된다. abs(2*x - K)로 잡으면 나눗셈을 피할수 있어서 좀더 낫다.

코드

"""Solution code for "BOJ 9024. 두 수의 합".

- Problem link: https://www.acmicpc.net/problem/9024
- Solution link: http://www.teferi.net/ps/problems/boj/9024

Tags: [Sort]
"""


def main():
    t = int(input())
    for _ in range(t):
        # pylint: disable=unused-variable
        n, K = [int(x) for x in input().split()]
        nums = [int(x) for x in input().split()]

        nums.sort(key=lambda x, k=K: abs(x + x - k))
        sums = [abs(x + y - K) for x, y in zip(nums, nums[1:])]
        print(sums.count(min(sums)))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Q I Z Q N
 
ps/problems/boj/9024.txt · 마지막으로 수정됨: 2021/09/21 14:01 저자 teferi