# [이.취.코] Chap 11. 그리디 - Q5. 볼링공 고르기

- Author: @mildsalmon
- Published: 2021-09-07
- Updated: 2021-09-07
- Source: http://blex.me/@mildsalmon/chap-11-%EA%B7%B8%EB%A6%AC%EB%94%94-q5-%EB%B3%BC%EB%A7%81%EA%B3%B5-%EA%B3%A0%EB%A5%B4%EA%B8%B0
- Tags: 파이썬, 한빛미디어, 나동빈, 코딩테스트, 문제, 그리디, 풀이, 볼링공고르기

---

# 1. 볼링공 고르기

- 난이도
	- 하
- 풀이 시간
	- 30분
- 시간 제한
	- 1초
- 메모리 제한
	- 128 MB
- 출처
	- 2019 SW 마에스트로 입학 테스트

### A. 문제

A, B 두 사람이 볼링을 치고 있다.  
두 사람은 서로 무게가 다른 볼링공을 고르려고 한다.  
볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여된다. 또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주한다.  
볼링공의 무게는 1~M까지의 자연수 형태로 존재한다.

##### a. 예를 들면. 

N = 5, M = 3이며 무게가 1, 3, 2, 3, 2일 때 각 공의 번호가 차례대로 1, 2, 3, 4, 5번으로 부여된다. 이때 두 사람이 고를 수 있는 볼링공의 조합을 구하면, 아래와 같다.

(1번, 2번), (1번, 3번), (1번, 4번), (1번, 5번), (2번, 3번), (2번, 5번), (3번, 4번), (4번, 5번)

두 사람이 공을 고를 수 있는 경우의 수는 8가지이다.

##### b. 입력 조건

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

##### c. 출력 조건

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

##### d. 테스트 케이스

- 입력 예시

	```

	5 3
	1 3 2 3 2

	```

	```

	8 5
	1 5 4 3 2 4 5 2
	
	```

- 출력 예시

	```

	8

	```
	
	```

	25

	```
	
### B. 내 답안

##### a. 1차 시도 (내가 생각해본 반례에서 틀림)

```python

from itertools import combinations  
  
n, m = list(map(int, input().split()))  
array = list(map(int, input().split()))  
count_sort = [0] * (m+1)  
result = 0  
  
for i in array:  
    count_sort[i] += 1  
  
for i in range(1, len(count_sort)):  
    if count_sort[i] > 0:  
        count_sort[i] -= 1  
print(count_sort)  
for i in count_sort:  
    if i < 2:  
        result += i  
    else:  
        result *= i  
print(result)  
result = len(list(combinations(array, 2))) - result  
  
print(result)

```

##### b. 2차 시도 (통과)

```python

from itertools import combinations  
  
n, m = list(map(int, input().split()))  
array = list(map(int, input().split()))  
result = 0

combi = list(combinations(array, 2))  
# print(combi)  
  
answer = len(combi)  
  
for i in combi:  
   A, B = i  
   if A == B:  
       answer -= 1  
  
print(answer)

```

##### c. 반례

```

# 반례  

# 5 3  
# 1 1 1 2 3 

# 10 8  
# 1 1 2 3 3 8 4 8 8 2

```

##### a. 회고

> 풀이

- 조합이라는 단어가 있길래, Combination이 떠올랐다.
- 하지만, 기존 Combination에서 조건이 하나 더 추가된다.
	- 두 사람이 고른 볼링공의 무게가 같으면 안된다.
- 즉, N개의 볼링공의 조합을 구한다. -> 구한 조합에서 볼링공의 무게가 같은 경우를 제외한다.
	- list의 pop() 메소드를 사용하려다가, 쓸데없이 시간 복잡도가 증가할 것으로 생각하여, 간단하게 len()을 사용하였다.
		- list메소드의 시간복잡도는 len()은 O(1), pop(i)는 O(N)이다.

![](https://static.blex.me/images/content/2021/9/8/8_8980sJlOeabohcLO8SmS.jpg)

> 반성

- 단순히 문제에서 예시로 나온 테스트 케이스에 맞추는데 집중했다. 그래서 반례에는 통과하지 못했다.

> 결론

- 조금만 더 생각해보자. 이번 문제에서는 추가 조건을 어떻게 해석하느냐에 따라 정답과 오답이 갈리는 문제였다.

### C. 문제 해설

> 제 풀이랑 조금 다른 방식입니다.

무게마다 볼링공이 몇 개 있는지를 계산해야 한다.

- 무게가 1인 볼링공 : 1개
- 무게가 2인 볼링공 : 2개
- 무게가 3인 볼링공 : 2개

A가 특정한 무게의 볼링공을 선택했을 때, 이어서 B가 볼링공을 선택하는 경우를 차례대로 계산하면 문제를 해결할 수 있다.  

1. A가 무게가 1인 공을 선택할 때의 경우의 수
	- 1 (무개가 1인 공의 개수) \* 4 (B가 선택하는 경우의 수) = 4가지
2. A가 무게가 2인 공을 선택할 때의 경우의 수
	- 2 (무개가 2인 공의 개수) \* 2 (B가 선택하는 경우의 수) = 4가지
3. A가 무게가 3인 공을 선택할 때의 경우의 수
	- 2 (무개가 3인 공의 개수) \* 0 (B가 선택하는 경우의 수) = 0가지

단계가 진행됨에 따라, 이미 계산했던 경우(조합)는 제외하기 때문에 B가 선택할 수 있는 경우의 수는 줄어든다.  
또한 볼링공의 무게가 1부터 10까지만 존재할 수 있기 때문에, 하나의 리스트를 선언하여 각 무게별로 볼링공이 몇 개가 존재하는지 기록할 수 있다.

##### a. 책 답안

[python-for-coding-test/5.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/11/5.py)

# 참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년