[ 이것이 코딩테스트다 ] 볼링공 고르기 - 그리디 알고리즘

[  이것이 취업을 위한 코딩테스트다 with 파이썬  ] 볼링공 고르기_ Python 파이썬

 

" 문제 "

 

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

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

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

볼링공의 무게는 1부터 M까지의 자연수 형태로 존재합니다.
예를 들어 N이 5이고, M이 3이며 각각의 무게가 차례대로 1, 3, 2, 3, 2일 때 각 공의 번호가 차례대로 1번부터 5번까지 부여됩니다. 이때 두 사람이 고를 수 있는 볼링공 번호의 조합을 구하면 다음과 같습니다

 

 

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

 

결과적으로 두 사람이 공을 고르는 경우의 수는 8가지 입니다.

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

 

<입력 조건>

첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 각각 자연수 형태로 주어집니다.

(1<=N<=1,000, 1<=M<=10)

둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어집니다.

 

<출력 조건>

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

 

 

입력 예시 1	출력 예시 1
5 3 1 3 2 3 2	8

입력 예시 2	출력 예시 2
8 5 1 5 4 3 2 4 5 2	25

---

" 아이디어 "

 

이 문제를 푸는 방법은 여러가지가 있겠지만 복잡도 O(n^2) 를 넘기고 싶지 않아서 최대한 루프 중첩을 피하는 방법을 생각해보았다.

 

1. 이중루프 피하기 / 2. 최대무게 m 활용하기

이 두가지 규칙을 세우고 풀이했다.

 

우선, ball_list (볼링공 리스트) 를 돌면서 weight_list (각 무게 당 볼링공의 개수) 를 구한다.

이때, 0kg인 볼링공은 없으므로 weight_list[0] 은 0으로 비워둔다.

 

예를 들어

weight_list = [0, 1, 2, 2] 인 경우

1kg = 1개

2kg = 2개

3kg = 2개

이런 식으로 볼링공이 구성되어 있는 것이다.

 

그다음, weight_list 를 돌면서 볼링공을 선택하는 경우의 수를 구하면 된다.

문제에서 무게가 같더라도 볼링공은 다른 것으로 간주한다고 하였으므로,

for 루프를 돌면서 다음 두가지 방법을 이용하여 경우의 수를 구하면 된다.

 

(1) 전체 개수에서 첫번째 사람이 고른 볼링공의 갯수 제외하기

n -= weight_list[i]

 

(2) 고르는 갯수 카운트하기

cnt += weight_list[i] * n

을 해주면 된다.

---

" 코드 "

n, m = map(int, input().split())
ball_weight = list(map(int, input().split()))
weight_list  = [0]*(m+1)
 
for weight in ball_weight:
  weight_list[weight] += 1
 
cnt = 0
for i in range(1, m+1):
  n -= weight_list[i]
  cnt += weight_list[i] * n
 
print(cnt)

---

" 참고자료 "