직각 삼각형
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 3000 |
| 문제명 | 직각 삼각형 |
| 레벨 | 실버 1 |
| 분류 |
기하학 |
| 시간복잡도 | O(n) |
| 인풋사이즈 | n<=100,000 |
| 사용한 언어 | Python 3.13 |
| 제출기록 | 53760KB / 172ms |
| 최고기록 | 100ms |
| 해결날짜 | 2025/02/18 |
풀이
직각 삼각형의 개수 와 비슷해보이지만, 축에 평행한 직각삼각형만 세면 된다는 조건이 들어가기 때문에 훨씬 간단하다.- 한 점을 고정했을때, 그 점과 x값이 같은 점 한개와 y값이 같은 점 한개를 찾으면 그 점을 직각인 꼭짓점으로 갖는 직각삼각형을 찾을 수 있다.
- 결국, 점 P를 직각인 꼭짓점으로 갖는 직각삼각형의 개수는, {P와 x좌표가 같은 점의 개수} * {P와 y좌표가 같은 점의 개수}로 계산할수 있다. x좌표 값마다 점의 개수를 세어놓은 딕셔너리와, y좌표 값마다 점의 개수를 세어놓은 딕셔너리를 미리 O(N)에 만들어 놓는다면, 특정 점을 직각인 꼭짓점으로 갖는 직각삼각형의 개수를 O(1)에 계산 가능하다. 이것을 N개의 점에 대해서 모두 구하면 O(N)이 걸린다.
코드
"""Solution code for "BOJ 3000. 직각 삼각형".
- Problem link: https://www.acmicpc.net/problem/3000
- Solution link: http://www.teferi.net/ps/problems/boj/3000
Tags: [geometry]
"""
import collections
import sys
def main():
N = int(sys.stdin.readline())
X_and_Y = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]
x_counter = collections.Counter(x for x, y in X_and_Y)
y_counter = collections.Counter(y for x, y in X_and_Y)
answer = sum(
(x_counter[x_i] - 1) * (y_counter[y_i] - 1) for x_i, y_i in X_and_Y
)
print(answer)
if __name__ == '__main__':
main()