볼링공 고르기

“이것이 코딩 테스트다”책에 있는 “2019 SW 마에스트로 입학 테스트”에서 출제한 볼링공 고르기 문제를 풀면서 조합 과 관련된 내용이 나왔다.
파이썬에는 순열과 조합에 관한 함수가 존재하는데 itertools에서 import 받아서 사용되는 permutations , combinations 이다. 처음 이 함수들을 사용하여 문제를 풀었다..

굉장히 비효율적인 코드이다.. 그리고 값이 커지면 제대로 된 답도 나오지 않았다.. 문제의 의도가 리스트의 처음값부터 마지막값까지 서로의 값들을 조합하여 값이 똑같은 경우를 제외한 값들만 출력을 하는거였다.

예를 들자면 1, 3, 1 의 무게를 가지는 공을 차례대로 조합을 하면 (1, 3), (1, 1), (3, 1)가 나오는데 이때 똑값은 값인 (1, 1)을 제외한 (1, 3), (3, 1) 을 출력해야 했다.. 주어진 값이 적을때는 효율성도 괜찮고 정확한 값이 출력되지만 조합이 되는 개수가 100개가 되고 1000개가 되면,,, 아예 돌아가지 않았고 심지어는 값도 정확하게 나오지 않았다… ^^

# 굉장히 비효율적인 코드 


from itertools import combinations 
import time

start_time = time.time()
n, m = map(str, input().split())
num_list = list(map(str, input().split()))
item_list = list(map(''.join, combinations(num_list, 2)))
[item_list.remove(i) for i in item_list if i[0] == i[1]]
print(len(item_list))

end_time = time.time()
print('프로그램 수행 시간 : {}'.format(end_time - start_time))

순열과 조합에 대해 찾아보니 itertools에서 제공되는 이 함수들은 코테를 볼 때 거의 사용하지 않는다고 한다. 개수가 약간 많아져도 시간복잡도가 상당하기 때문에 이 함수를 사용하는 것은 매우 비효율적일뿐 아니라 0점을 맞을 확률이 99.9%였다..

그렇다면 이런 조합(or순열)에 관한 문제들은 어떻게 풀어야 하는가.. 수학적 공식을 알고 있으면 좀 더 간단하고 빠르게 풀 수 있었다. 조합은 nCr 이며 이는 n * (n - 1) / 2 의 공식과 같다. 이 수학적 공식을 이용해보자. 아이디어는

두 사람이 볼링공 무게와 상관 없이 모든 볼링공을 고르는 경우의 수를 구한다
두 사람이 고르는 볼링공의 무게가 같은 경우의 수를 구한다. (nCr의 공식을 가지고 구현한다)
전체의 경우의 수에서 2의 경우의 수를 빼준 후 값을 출력한다

문제 풀이

1.공의 개수 n과 무게의 범위 m, 공의 무게가 나열되어 있는 리스트 weight_list을 구현한다

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

2.nCr의 공식을 변수에 선언한다

total = N * (N - 1) / 2

3.같은 무게의 공을 고르는 경우의 수를 고른다.

우선 무게의 범위를 기준으로 반복을 돌리면서 가장 무게가 적게 나가는 값부터 비교를 시작한다. 예를 들어 i = 2로 2의 무게를 가지는 공의 개수를 count(m)를 이용해 구해준다. 만약 똑같은 무게를 가지는 공이 2개가 존재한다면 same_ball_sum에는 2가 들어갈 것이다. 그렇다면 이후 if문의 조건에 걸리게 되고 조합의 공식을 이용하여 5 * (5 - 1) / 2 - 2 * (2 - 1) / 2 을 계산하면 된다. 10 -1 = 9가 된다. 이후 for문을 돌면서 똑같은 처리를 해주면 same_weight에는 두 사람이 같은 무게의 공을 고를 경우의 수의 합계가 들어간다.

same_weight = 0
for i in range(1, m + 1):
  same_ball_sum = weight_list.count(m)
  if same_ball_sum > 1:
    same_weight += same_ball_sum * ( same_ball_sum -1) / 2

print(int(total - same_weight)

위의 코드는 블로그를 찾아보다 괜찮은 방법인 것 같아서 공부했었다. 책에는 아래의 코드와 같이 작성되었다. 음,, 사실 아래의 코드보다는 위의 코드가 더 이해가 잘 가는 것 같다.. 아래에서는 공의 최대 무게를 이용해 미리 리스트에 공간을 할당해주었다(공의 최대 무게 10) 이후 공의 무게가 나열되어 있는 리스트의 반복을 돌면서 각 요소값에 1씩 더해준 후 array를 업데이트 시켜주었다 (array에는 실제 공의 무게가 존재하는 요소에만 1이 더해진다) 이후에 무게를 기준으로 반복을 돌면서 무게가 i인 볼링공의 개수를 n에서 제외시켰다(A가 선택할 수 있는 개수라고 한다….) 이후 B가 선택하는 경우의 수와 곱해준후 값을 result에 담아주고 출력한다

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

array =[0] * 11

for x in data:
    array[x] += 1
    
result = 0

for i in range(1, m + 1):
    n -= array[i]
    result += array[i] * n
print(result)