테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 두 수의 합 ======

===== 풀이 =====
  * 정렬해서 [[ps:투 포인터]]를 사용해도 되지만, 그냥 해시 테이블에 모든 수와 등장 횟수를 저장하면, 어떤 a_i에 대해서 X-a_i 가 몇개나 존재하는지를 O(1)에 구할 수 있다. 
  * 이렇게 하면, 전체 시간복잡도는 해시테이블 구축에 O(n), 탐색에 O(n), 전체 O(n)이 된다. 
  * 모든 수에 대해서 등장 횟수를 해시테이블에 저장하는 것은 그냥 collections.Counter를 쓰면 된다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 3273. 두 수의 합".

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

import collections


def main():
    n = int(input())  # pylint: disable=unused-variable
    a = [int(x) for x in input().split()]
    x = int(input())

    counter = collections.Counter(a)
    answer = sum(c * counter[x - v] for v, c in counter.items() if v + v < x)
    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_3}}