[이코테] 그리디 - 볼링공 고르기

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

A, B 두 사람이 볼링을 치고 있다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 한다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여된다. 또한 같은 무게의 공이 여러개 있을 수 있지만, 서로 다른 것으로 간주한다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다. 예를 들어, N이 5이고, M이 3이며, 각각의 무게가 차례대로 [1, 3, 2, 3, 2] 일때 각 공의 번호가 차례대로 1번부터 5번까지 부여한다. 이 때 두 사람이 서로 다른 공을 고를 수 있는 경우의 수는 총 8가지이다. N개의 공의 무게가 각각 주어질때, 두 사람이 볼링공을 고르는 경우의 수를 구해라.

입력조건

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

출력조건

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

사고과정

• 공 무게 정보 배열을 입력받을때, 그 배열의 인덱스를 공의 번호로 하면 되겠다고 생각했다. 그리고 주어진 데이터 범위가 1000으로 그다지 많지 않다고 생각해서 조합 라이브러리를 이용해 모든 조합을 만든다음 하나씩 돌면서 각 조합에서 나온 공 번호 2개를 인덱스로 해서 처음에 입력받은 무게 정보 배열을 참조해서 두 개가 같으면 세지 않고, 다르면 세는 방식으로 경우의 수를 셋다.(책 속 입력 예시는 맞았긴 한데, 다른 테스트 케이스가 없어서 정답을 100%확신하지는 못했다..)
• 책 풀이를 보니 조합라이브러리를 사용하지 않았다. 우선 똑같은 무게의 공들이 여럿있을 수 있으니 무게 별로 공의 개수가 무엇인지 계산했다. 그리고 A가 먼저 특정 공을 선택했을 때, B가 선택할 수 있는 경우의 수를 구해 총 경우의수를 계산했다. A가 먼저 공을 선택하면 B가 선택할 때는 경우의 수가 줄어들 수 밖에 없는데, 이유는 '조합'을 구하는 문제 요구사항 때문이다.

풀이

1. 스스로 푼 풀이

from itertools import combinations

n, m = map(int, input().split())
array = [0]
for d in list(map(int, input().split())):
    array.append(d)

count = 0
for comb in list(combinations([x for x in range(1, n+1)], 2)):
    a, b = comb[0], comb[1]
    if array[a] != array[b]:
        count += 1

print(count)

2. 책 속 풀이(이걸로 풀어보는 연습하기)

import sys

n, m = map(int, input().split())
# 각 공의 무게 정보
weights = list(map(int, input().split()))

# idx를 무게로 하고 value를 그 무게의 공 개수로 하는 array 초기화(주이전 범위의 무게 최댓값은 10임)
array = [0] * 11
for w in weights:
    array[w] += 1

# A가 선택하면 B가 선택할 수 있는 경우의 수는 줄어듦(왜냐면 중복되는 경우의 수는 피해야 하는 조합이니까)
result = 0
# array[i]는 A가 고르는 공을 의미
for i in range(1, m+1):
    n -= array[i]  # 업데이트 된 n은 B가 고를수 있는 경우의 수
    result += array[i] * n

print(result)