그리디 : 볼링공 고르기

문제

• 서로 무게가 다른 볼링공을 골라야 함
• 볼링공 N개 , 무게는 1~M
• 두 사람이 볼링공을 고르는 경우의 수

내 풀이

1. N,M 을 입력받기 / list_N 입력받기
2. list_N 을 정렬
3. 2중 for문을 돌면서
   -- list_N[i]와 list_N[j]이 같으면 패스
   -- 없으면 total += 1

N,M = map(int,input().split())
list_N = list(map(int,input().split()))
total = 0

for i in range(len(list_N)):
  for j in range(i, len(list_N)):
    if list_N[i] != list_N[j]:
      total += 1

print(total)

25/03/06

고민

• 똑같이 2중 for문으로 풀었다,,,
• 챗지피티에게 물어보니 아래와 같은 코드를 추천해줌ㅠ

# 입력 받기
N, M = map(int, input().split())  # 볼링공 개수, 무게의 범위
balls = list(map(int, input().split()))  # 볼링공의 무게 리스트

# 1️⃣ 무게별 볼링공 개수 세기
count_by_weight = [0] * (M + 1)  # 무게별 개수 저장할 리스트

for ball in balls:
    count_by_weight[ball] += 1

# 2️⃣ 전체 조합 계산 (O(N))
total_pairs = (N * (N - 1)) // 2  # 전체 가능한 조합 개수 (nC2)
same_weight_pairs = 0  # 같은 무게의 볼링공을 선택하는 경우의 수

for weight in range(1, M + 1):
    if count_by_weight[weight] > 1:  # 같은 무게가 2개 이상이면
        same_weight_pairs += (count_by_weight[weight] * (count_by_weight[weight] - 1)) // 2  # 같은 무게끼리 선택하는 경우

# 3️⃣ 다른 무게의 공을 선택하는 경우의 수 = 전체 조합 - 같은 무게 조합
result = total_pairs - same_weight_pairs

print(result)