볼링공 고르기 코드 및 해설 (파이썬)

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 5, p 315

 

먼저 무게에 상관없이 두 사람이 볼링공을 고르는 경우의 수를 구해 total에 저장합니다. 이는 nC2와 같으므로 n * (n-1) / 2로 구현합니다. 이후 같은 무게의 공이 2개 이상인 공들을 확인하며, 이 두개를 두 사람이 고를 경우의 수를 구해 duplicates에 저장합니다. total에서 duplicates를 뺀 값을 최종 정답으로 반환합니다.

 

import sys
# N: 공의 개수, M: 무게의 범위
N, M = map(int, sys.stdin.readline().split())
balls = list(map(int, sys.stdin.readline().split()))

# nC2
total = N * (N-1) / 2

# 같은 무게의 공을 고르는 경우 
duplicates = 0
for m in range(1, M+1):
    dups = balls.count(m)
    if dups > 1:
        # dups C 2 
        duplicates += dups * (dups-1) / 2

print(int(total - duplicates))