ps:problems:boj:3273
두 수의 합
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 3273 |
문제명 | 두 수의 합 |
레벨 | 실버 3 |
시간복잡도 | O(n) |
인풋사이즈 | n<=1000000 |
사용한 언어 | Python |
제출기록 | 44876KB / 164ms |
최고기록 | 96ms |
해결날짜 | 2021/08/03 |
풀이
- 정렬해서 투 포인터를 사용해도 되지만, 그냥 해시 테이블에 모든 수와 등장 횟수를 저장하면, 어떤 a_i에 대해서 X-a_i 가 몇개나 존재하는지를 O(1)에 구할 수 있다.
- 이렇게 하면, 전체 시간복잡도는 해시테이블 구축에 O(n), 탐색에 O(n), 전체 O(n)이 된다.
- 모든 수에 대해서 등장 횟수를 해시테이블에 저장하는 것은 그냥 collections.Counter를 쓰면 된다.
코드
"""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()
ps/problems/boj/3273.txt · 마지막으로 수정됨: 2021/09/16 16:49 저자 teferi
토론