[이코테] 볼링공 고르기

이것이 취업을 위한 코딩테스트다 with 파이썬 책을 읽고 정리한 내용입니다.

 

 

 

 

📋 문제

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 <= K <= M)

 

 

👈 출력

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

 

 

📝 풀이

import sys
from itertools import combinations
input = sys.stdin.readline

n, m = map(int, input().split())
arr = list(input().split())
print(len(list(filter(lambda x: x[0] != x[1], combinations(arr, 2)))))

 

메모리랑 시간 제한을 통과할지는 모르겠는데 아무튼 조합을 이용한 풀이이다.

n, m, arr에 각 입력을 받고 arr의 가능한 모든 조합을 구한 뒤 이 둘의 무게가 일치하지 않는 것만 골라 그 수를 셌다.

 

 

💯 정답

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

weight = [0] * 11
for x in arr:
  weight[x] += 1

answer = 0
for i in range(1, m+1):
  n -= weight[i]
  answer += weight[i] * n

print(answer)

 

그리디를 이용한 풀이이다.

n, m, arr에 각 입력을 받는다.

 

weight이라는 공의 무게를 담을 리스트를 선언하는데 공의 무게가 1부터 10까지 있으므로 길이가 11인 리스트로 초기화한 후 for문을 돌며 해당 무게의 공이 몇 개가 있는지 개수를 세 weight에 저장한다.

 

다시 for문을 돌며 A와 B가 선택할 수 있는 경우의 수를 계산한다.

먼저 n에서 weight[i]를 빼는 것은 A가 선택할 수 있는 경우의 수를 제외하는 것이다.

그리고 여기에 weight을 곱하면 우리가 원하는 경우의 수를 얻을 수 있다.

 

 

🔍 참조

이것이 취업을 위한 코딩 테스트다 with 파이썬 (한빛미디어, 나동빈)