[이것이 코딩테스트다] 볼링공 고르기

문제

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

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

 

입력 조건

• 첫쨰줄에 볼링공의 개수 n, 공의 최대 무게 m이 공백으로 구분되어 각각 자연수 형태로 주어집니다. (1<=n<=1000, 1<=m<=10)
• 둘째줄에 각 볼링공의무게 k가 공백으로 구분되어 순서대로 자연수 형태로 주어집니다.(1<=k<=m)

출력 조건

첫쨰줄에 두 사람이 볼링공을 고르는 경우의수를 출력

 

예시

5 3

1 3 2 3 2

 

출력 

8

 

해결  방법

같은 무게여도 다른 공으로 취급한다고 했으니 뽑은 볼링공의 무게와 다르기만 하면 뽑는 횟수에 추가한다. 

즉 1 3 2 3 2 일때 1의 무게를 가지는 1번째 볼링공은 2,3,4,5번과 함께 조합이 가능한 것이고,

3의 무게를 가지는 2번 공은 같은 무게인 4번공을 제외한 3번과 5번과 조합이 가능하다.

2의 무게를 가지는 3번 공은 같은 무게인 5번공을 제외한 4번과 조합이 가능하고 4번공은 5번공과 조합이 가능하여 총 8가지로 조합할 수 있는 것이다.

 

무게를 담은 볼링공 리스트를 큐로 변환해서 처음부터 뽑아가며 다른 공들을 하나씩 비교하면서 같은 무게인지 확인하고 다른 무게라면 카운트를 세는 방식으로 문제를 풀었다.

 

코드

from collections import deque

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


q=deque(s)
cnt=0
while q :
    temp=q.popleft()
    for i in q :
        if i!=temp :
            cnt+=1

print(cnt)

 

<책에서의 풀이>

무게마다 볼링공의 갯수가 몇개인지 확인 후, 특정한 무게의 볼링공을 선택했을 때 차례대로 계산하는 방식을 사용했다.

문제 예시를 들어 설명하면

 

• 무게가 1인 볼링공 갯수 : 1
• 무게가 2인 볼링공 갯수 : 2
• 무게가 3인 볼링공 갯수 : 2

a가 무게가 1인 볼링공을 뽑을때 경우의 수  : 1x4=4

a가 무게가 2인 볼링공을 뽑을때 경우의 수  : 2x2=4

a가 무게가 3인 볼링공을 뽑을때 경우의 수  : 2x0=0

 

볼링공 무게가 10까지로 정해졌으므로 1부터 10까지 담을 수 있는 리스트를 0으로 초기화한 후 볼링공 갯수를 기록한다.

 

코드

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

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

#볼링공 무게 기록
for x in s :
    array[x]+=1 

result =0

for i in range(1, m+1) :
    n-=array[i] #무게가 i인 볼링공의 개수 제외
    result+=array[i]*n #b가 선택한 경우의 수와 곱하기

print(result)

※<이것이 취업을 위한 코딩테스트다 (나동빈 저)> 를 참고하여 작성된 게시글입니다.