[그리디 Greedy] 볼링공 고르기

문제

A, B 두 사람이 볼링을 치고 있다. 두 사람은 무게가 서로 무게가 다른 공을 고르려고 한다.

볼링공은 총 N개 있으며 각 볼링공마다 무게가 적혀있고, 공의 번호는 1번부터 순서대로 부여된다.

또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주한다.

볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다.

N개의 공의 무게가 각각 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하시오.

단, (1번공, 2번공)과 (2번공, 1번공)은 같은 경우로 간주한다.

입력 조건

첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 자연수 형태로 주어진다. (1<=N<=1,000, 1<=M<=10)
둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어진다.(1<=K<=M)

출력 조건

첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력한다.

입력 예시

5 3

1 3 2 3 2

출력 예시

✔ Solution - dictionary 이용

n, m = map(int, input().split())
weight = list(map(int, input().split()))

dic = {} # key = weight, value = 볼링공의 수
for i in range(m):
    dic[i + 1] = weight.count(i + 1)

result = 0

for i in range(1, m + 1):
    # 무게가 i인 공의 개수를 제외
    n -= dic[i]
    # 다른 사람이 고를 수 있는 공의 수와 곱해줌
    result += dic[i] * n
    
print(result)

⭐ 문제 포인트

무게가 다른 볼링공을 골라야 한다.
무게마다 몇개의 볼링공이 존재하는지 저장해준다.
A가 먼저 볼링공을 선택했을 때, B가 다른 공을 고를 경우를 고려한다.
이미 계산한 조합은 제외를 해야한다.

✔ Solution 2 - 계수 정렬 이용

n, m = map(int, input().split())
weight = list(map(int, input().split()))

# 볼링공의 무게에 해당하는 공의 수를 넣어줄 리스트
weight_count = [0] * 11

for i in weight:
    # 볼링공의 무게에 해당하는 공의 수를 담아준다.
    weight_count[i] += 1

result = 0

for i in range(1, m + 1):
    # 무게가 i인 공의 개수를 제외
    n -= weight_count[i]
    # 다른 사람이 고를 수 있는 공의 수와 곱해줌
    result += weight_count[i] * n
    
print(result)

✔ Solution 3 - combinations 모듈 사용

from itertools import combinations

n, m = map(int, input().split())
weight = list(map(int, input().split()))

result = 0
# 볼링공의 무게가 다를때의 조합
for a, b in combinations(weight, 2):
    if a != b:
        result += 1

print(result)