[Baekjoon] 20943번 카카오톡

문제

카카오톡은 주식회사 카카오가 2010년 3월 18일 서비스를 시작한 글로벌 모바일 인스턴트 메신저로, 2020년 기준 4000만 명의 사용자가 등록돼 있고 시장 점유율이 96%로 사실상 거의 모든 국민이 사용할 정도로 점유율이 매우 높다.

카카오는 이번에 Sinchon ICPC을 지원해 주는 대가로 출제진인 국렬이에게 카카오톡의 특이한 오픈톡방에 대한 실험 결과를 요구하였다. 실험에 대한 내용은 다음과 같다.

1. N명의 유저가 모인 특이한 오픈톡방이 있다.
2. 특이한 오픈톡방은 하나의 좌표 평면으로 구성되어 있으며, 각각 유저들은 좌표 평면 상의 서로 다른 직선 1개를 할당받는다.
3. 각 유저들이 서로의 톡을 보기 위해서는 각 유저들의 직선이 서로 만나야 한다. 서로 만나지 않는다면 서로의 톡을 볼 수 없다.

이때, 국렬이는 특이한 오픈톡방 내에서 서로의 톡을 확인할 수 있는 유저의 쌍의 수를 구해야 한다. 국렬이는 너무 게을러서 이 실험을 대회에 떠넘겨버렸다. 당신은 상금을 위해 이 문제를 해결해야 한다.

입력

다음과 같이 입력이 주어진다.

$N$

$a_1\, b_1\, c_1$ … $a_N\, b_N\, c_N$

• N은 오픈 톡방에 모인 사람의 수를 의미하는 양의 정수다. (1≤N≤500000)
• aix+biy+ci=0은 i번째 유저가 할당받은 직선이다. (1≤$i$≤$N$)
• $−10^9$≤$a_i,b_i,c_i$≤$10^9$ (1≤$i$≤$N$)
• ($a_i,b_i$)≠(0,0) (1≤$i$≤$N$)
• 다수의 유저들이 동일한 직선을 할당받는 경우는 존재하지 않는다.
• 입력으로 주어지는 모든 수는 정수다.

출력

서로의 톡을 확인할 수 있는 유저의 쌍의 수를 출력하여라.

예제

Example 1:

Input: 
4
1 2 3
2 4 5
1 3 6
3 9 7
Output: 
4

Example 2:

Input:
3
1 2 3
-1 -2 3
1 -2 3
Output:
2

조건

시간 제한 : 2초

메모리 제한 : 1024 MB

풀이과정

내 풀이

import sys
import operator as op
from functools import reduce
input = sys.stdin.readline

# n = 사람 수
n = int(input())

# 딕셔너리 생성
check = dict()

# 딕셔너리를 통해 기울기 개수 세기
for i in range(n):
    a, b, c = map(int ,input().split())
    if b != 0:
        if a == 0:
            if 0 not in check:
                check[0] = 1
            else:
                check[0] += 1
        else:
            if -(a/b) not in check:
                check[-(a/b)] = 1
            else:
                check[-(a/b)] += 1
    else:
        if a == 0:
            if 0 not in check:
                check[0] = 1
            else:
                check[0] += 1
        else:
            if int(1e9) not in check:
                check[int(1e9)] = 1
            else:
                check[int(1e9)] += 1

# 조합 정의
def nCr(n, r):
    if n < 1 or r < 0 or n < r:
        return 0
    r = min(r, n-r)
    numerator = reduce(op.mul, range(n, n-r, -1), 1)
    denominator = reduce(op.mul, range(1, r+1), 1)
    return numerator // denominator

# 중복된 개수를 리스트로 받아오기
sub = list(check.values())

# 전체 쌍을 짓는 개수 - 기울기가 같은 쌍이 생성되는 개수
cnt = nCr(n,2)
for i in sub:
    if i >= 2:
        cnt -= nCr(i,2)

print(cnt)

백준 저지사이트 대회에 잠깐 참가했다. 이 문제의 포인트는 기울기이다. 기울기가 같다면 만나지 않는다. 특히 다수의 유저들이 동일한 직선을 할당받는 경우가 존재하지 않기 때문에 기울기가 같을 때 겹쳐서 만나는 경우는 생각하지 않아도 된다.

그래서 처음에는 기울기를 다 입력받고 for문을 2번 돌렸다. 하지만 시간 초과가 나왔고 어떻게 해야될지 고민하다가 딕셔너리 자료형으로 입력받으면서 개수를 세고 조합에 대한 함수를 만들고 (대회중이라 구글링으로 해결) 전체 쌍을 짓는 개수에서 기울기가 같은 쌍이 생성되는 개수만큼 빼면 답이 된다.