사용자 도구

사이트 도구


ps:problems:boj:2470

두 용액

ps
링크acmicpc.net/…
출처BOJ
문제 번호2470
문제명두 용액
레벨골드 5
분류

정렬

시간복잡도O(nlogn)
인풋사이즈n<=100,000
사용한 언어Python
제출기록40768KB / 156ms
최고기록116ms
해결날짜2021/08/03

풀이

  • 두 수의 합 처럼 두 수의 합이 X가 되는 쌍을 찾는 문제를 풀기 위해서는 소팅과 투 포인터를 안쓰고도 그냥 해싱을 통해서 푸는 것이 더 빨랐다. 그러나 이 문제처럼 두 수의 합이 X에 가장 가까운 쌍을 찾는 문제라면, 소팅 후에 투 포인터이진 검색 (Binary search)을 써야 한다.
  • 투 포인터 방법은 소팅 후에 양 끝에서 출발하는 포인터 2개를 갱신해 나가는 것. 합이 X보다 작으면 왼쪽 포인터를 증가시키고, 합이 X보다 크면 오른쪽 포인터를 감소시킨다. 이 방식으로는 소팅에 O(nlogn), 탐색에 O(n), 총 O(nlogn)에 풀수 있다.
  • 이진 검색은, 정렬 후에 각 숫자 X에 대해서 -X에 가장 가까운 값을 이분탐색으로 찾는 것을 반복하면 된다. 정렬에도 O(nlogn) 탐색에 O(nlogn)이 걸려서 총 시간 복잡도는 똑같이 O(nlogn)이지만, 좀더 느리다.
  • 그리고, 역시 시간 복잡도는 같지만 좀더 간단하게 구현 가능한 방법이 있다. 합이 0에 가장 가까운 두 수는 절대값을 기준으로 소팅했을때 인접한 위치에 존재한다. 따라서, 그냥 절대값을 기준으로 소팅하고 인접한 두 수들만 비교해주면 된다. 시간 복잡도는 역시 소팅에 O(nlogn), 탐색에 O(n), 총 O(nlogn).
  • 이 문제에서는 마지막 방식으로만 구현했다. 투포인터 방식으로 구현한 코드는 용액을 참고. 용액은 이 문제와 동일한데 데이터가 소팅이 된 채로 들어오는 것만 다르다.

코드

"""Solution code for "BOJ 2470. 두 용액".

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

Tags: [Sort]
"""


def main():
    N = int(input())
    nums = [int(x) for x in input().split()]

    nums.sort(key=abs)
    _, pair = min((abs(sum(pair)), pair) for pair in zip(nums, nums[1:]))

    print(*sorted(pair))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
P A L A Q
 
ps/problems/boj/2470.txt · 마지막으로 수정됨: 2021/09/17 13:44 저자 teferi