알고리즘 문제 - 볼링공 고르기

문제

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

 

예를 들어, N이 5이고, M이 3이며 각각의 무게가 차례대로 1,3,2,3,2일 때 두 사람이 공을 고르는 경우의 수는 8가지이다.

 

입력

첫 째줄 -> 볼링공의 개수 N(1 ~ 1000), 공의 최대 무게 M(1 ~ 10)
둘 째줄 -> 각 볼링공의 무게 K (1 ~ M)

 

출력

두 사람이 볼링공을 고르는 경우의 수

 

풀이

3가지 풀이를 해봤다.

 

1. 이중 loop

n,m=map(int,input().split())
data=list(map(int,input().split()))
result=0
for i in range(n-1):
  for j in range(i,n):
    if data[i] != data[j]:
      result+=1
print(result)

단순히 data를 이중 loop를 돌려서 서로 무게가 다르면 result 값을 증가하는 알고리즘이다.

-> O(n2)

 

2. 데이터 정렬 후 loop

n,m=map(int,input().split())
data=list(map(int,input().split()))
data.sort()
count=1
result=0
for i in range(n-1):
  if data[i]!=data[i+1]:
    result+=count*(n-i-1)
    count=1
  else:
    count+=1
print(result)

오름차순으로 정렬한 data를 탐색하면서 중복되는 무게 x의 개수(count)를 체크한다.

 

이 때, 다른 무게값이 탐색된다면 이전 무게 x의 개수와(count) 앞으로 남은 볼링공들의 개수를 곱한 값이 A가 무게 x를 선택했을 때 B가 다른 무게를 고를 경우의 수가 된다.

 

이를 바뀐 다른 무게에 대해서 반복한다.

-> O(nlogn)

 

3. 각 무게별 개수 측정

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

# 1부터 10까지의 무게를 담을 수 있는 리스트
array = [0] * 11

for x in data:
    # 각 무게에 해당하는 볼링공의 개수 카운트
    array[x] += 1

result = 0
# 1부터 m까지의 각 무게에 대하여 처리
for i in range(1, m + 1):
    n -= array[i] # 무게가 i인 볼링공의 개수(A가 선택할 수 있는 개수) 제외
    result += array[i] * n # B가 선택하는 경우의 수와 곱해주기

print(result)

 각 무게별로 개수를 저장하는 리스트를 만든다.

 

리스트에 각 무게에 해당하는 볼링공의 개수를 저장한다.

 

무게 1부터 무게 m까지 loop를 돌린다.

각 무게별로 풀이 2와 같이 무게 x인 볼링공의 개수와 남은 볼링공들의 개수를 곱한 값을 차근차근 더해준다. (주석 참고)

-> O(n)