평면 위의 평행선 개수 세기

평면 위에 주어진 점들을 지나는 x축 또는 y축에 평행한 직선의 개수를 세는 문제이다.

평면에 n개의 점이 있다. 그중 두 개 이상의 점을 지나면서 x축 또는 y축에 평행한 직선이 몇 개인지 알아내는 프로그램을 작성하시오.

입력:

• 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다.
• 다음 n개의 줄에는 각 점의 좌표가 주어진다.
• 같은 좌표가 여러 번 주어질 수 있으며, 그런 경우 서로 다른 점으로 간주한다.
• 좌표는 절댓값이 2^31보다 작은 정수이다.

출력: 첫째 줄에 답을 출력한다.

예시

입력:
4
0 0
10 10
0 10
10 0

출력:
4

1. x축에 평행한 직선은 y좌표가 같은 점들을 지나게 된다.
2. y축에 평행한 직선은 x좌표가 같은 점들을 지나게 된다.
3. 직선이 의미를 가지려면 적어도 두 개 이상의 점을 지나야 한다.

따라서 문제를 해결하는 핵심 아이디어를 아래와 같이 도출할 수 있다:

• 동일한 x좌표 값을 가진 점이 2개 이상 있으면 y축에 평행한 직선이 존재한다.
• 동일한 y좌표 값을 가진 점이 2개 이상 있으면 x축에 평행한 직선이 존재한다.

이 아이디어를 바탕으로 알고리즘을 작성해 보겠다.

해법

알고리즘은 다음과 같이 구현할 수 있다:

1. 각 x좌표와 y좌표가 나타나는 빈도를 계산한다.
2. x좌표가 2번 이상 나타나면, 해당 x좌표를 가진 점들을 지나는 y축에 평행한 직선이 1개 있다는 의미이다.
3. y좌표가 2번 이상 나타나면, 해당 y좌표를 가진 점들을 지나는 x축에 평행한 직선이 1개 있다는 의미이다.
4. 이렇게 조건을 만족하는 직선의 개수를 세면 된다.

구현

import sys

input = sys.stdin.readline

def solution():
    n = int(input())

    x_occurrence, y_occurrence = {}, {}

    for _ in range(n):
        x, y = input().split()
        if x in x_occurrence:
            x_occurrence[x] += 1
        else:
            x_occurrence[x] = 1

        if y in y_occurrence:
            y_occurrence[y] += 1
        else:
            y_occurrence[y] = 1

    x_items = list(filter(lambda item: item[1] >= 2, list(dict.items(x_occurrence))))
    y_items = list(filter(lambda item: item[1] >= 2, list(dict.items(y_occurrence))))

    print(len(x_items) + len(y_items))

if __name__ == '__main__':
    solution()

예제 입력인 (0,0), (10,10), (0,10), (10,0)를 살펴보자.

• x=0인 점: (0,0), (0,10) → 2개 → y축 평행선 1개
• x=10인 점: (10,10), (10,0) → 2개 → y축 평행선 1개
• y=0인 점: (0,0), (10,0) → 2개 → x축 평행선 1개
• y=10인 점: (10,10), (0,10) → 2개 → x축 평행선 1개

따라서 총 4개의 직선이 답이 된다.

시간 복잡도

• 좌표 빈도 계산: O(n)
• 직선 개수 세기: O(n)

따라서 전체 시간 복잡도는 O(n).