[이것이 코딩테스트다] Chapter11. Q8 볼링공 고르기
문제
A, B 두 사람이 볼링을 치고 있다. 두 사람이 서로 무게가 다른 볼링공을 고르려고 한다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여되된다. 같은 무게의 공은 여러 개가 있을 수 있지만, 서로 다른 공으로 간주한다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다.
예시
N=5이고M=3이며 각각의 무게가1, 3, 2, 3, 2일 때, 두 사람이 고를 수 있는 번호의 조합은(1,2) (1,3) (1,4) (1,5) (2,3) (2,5) (3,4) (4,5)로 총 8가지이다.
입력 조건
- 첫째 줄엔 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 주어진다.
(1<=N<=1,000), (1<=M<=10)- 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 주어진다.
(1<=K<=M)
출력 조건- 첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력한다.
Problem Solving
무게마다 볼링공이 몇 개 있는지를 계산하고 A가 특정한 무게의 볼링공을 선택했을 때, B가 볼링공을 선택하는 경우를 곱하여 문제를 해결 가능하다.
예시로 n=6 m=3 1 3 1 2 3 2이 입력값으로 주어졌다고 생각해본다.
-
먼저 각 무게마다 볼링공의 개수를 리스트에 저장한다.
-
A가 무게가 1인 공을 선택할 때의 경우의 수
2(무게가 1인 공의 개수) * 4(B가 선택하는 경우의 수) = 8 -
A가 무게가 2인 공을 선택할 때의 경우의 수
2(무게가 2인 공의 개수) * 2(B가 선택하는 경우의 수) = 2 -
A가 무게가 2인 공을 선택할 때의 경우의 수
2(무게가 3인 공의 개수) * 0(B가 선택하는 경우의 수) = 0
단계가 진행됨에 따라 B가 선택하는 경우의 수가 줄어드는데, 이미 계산한 조합은 제외하기 때문이다.
Python Code
n,m = map(int, input().split())
data = list(map(int, input().split()))
# 1부터 10까지의 무게를 담을 수 있는 리스트 생성
arr=[0]*10
for x in data:
#각 무게에 해당하는 볼링공 개수 카운트
arr[x-1]+=1
result=0
# 무게가 적은거부터 A가 선택한다고 가정
for i in range(m):
n -= arr[i] # A가 선택한 무게의 볼링공 개수를 전체 개수에서 제외
result += arr[i]*n # B가 선택하는 경우의 수와 곱하기
print(result)Discussion
My solution
n,m = map(int, input().split())
data = list(map(int, input().split()))
# #my solution_slow
data.sort()
count=0
for i in range(n):
for j in range(i+1,n):
if data[i]!=data[j]:
count+=1
print(count)해설을 보지 않고 푼 소스이다.
data를 정렬하고 data[i]는 A가 고른 볼링공 data[j]는 B가 고른 볼링공으로 가능한 모든 조합을 count하는 코드이다. 2중 for문이기에 실행속도가 해설보다 느리다.
# My code
for i in range(m):
result+= arr[i] * sum(arr[i+1:])
# Answer
for i in range(m):
n -= arr[i]
result += arr[i]*n답안 코드를 보지 않고 해설만 보고 구현해본 코드에서 답안처럼 하지 못한 부분이 있어 가져왔다. 리스트 슬라이싱으로 'B가 선택하는 경우의 수'를 계산했는데 n이 전체 개수이므로 현재 리스트 인덱스의 값을 빼가면 같은 값을 sum 함수 없이 편하게 알아낼 수 있다. 이 경우도 답안이 내 풀이보다 빠르게 문제를 해결할 수 있다.
References
- 나동빈, ⌜이것이 취업을 위한 코딩테스트다 with Python⌟, 한빛미디어, 2020, p.315
)
