볼링공 고르기 - 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가 공백으로 구분되어 순서대로 자연수 형태로 주어집니다.

출력 조건

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

입력 예시

5 3
1 3 2 3 2

출력 예시

8

입력 예시

8 5
1 5 4 3 2 4 5 2

출력 예시

25

풀이 1 핵심 아이디어

차례대로 탐색하면서 중복 제외하여 카운트

풀이 2 핵심 아이디어

A가 특정한 무게의 볼링공을 선택했을때 이어서 B가 볼링공을 선택하는 경우를 차례대로 계산

1의 무게 1개, 2의 무게 2개, 3의 무게 2개 경우

a가 1을 선택하면 b는 2,3무게의 4개 선택 가능하여 4개의 조합

a가 2를 선택하면 b는 3의 무게 선택 가능(1과 2무게 선택 불가)하여 총 4개의 조합

a가 3를 선택하면 b는 선택가능한 무게가 없으므로 0개의 조합

총 8개의 조합

PseudoCode

1번

1. 입력 (Input)
   • 공백 구분, 리스트로 입력 받음
2. 처리 (Process)
   • 이중 for 문으로 중복되지 않은 조합 카운트
3. 출력 (Output)
   • 카운트 출력

2번

1. 입력 (Input)
   • 공백 구분, 리스트로 입력 받음
2. 처리 (Process)
   • 1부터 10까지 무게를 담을 수 있는 리스트 선언
     • 각 무게에 해당하는 볼링공 수 카운트
   • for 문으로 1의 무게부터 m까지 차례대로
     • A가 선택한 무게의 볼링공 수 * B가 선택한 볼링공 수(A가 선택한 볼링공 수는 빼야함)
3. 출력 (Output)
   • 카운트 출력

문제 풀이

1번

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

print(count)

2번

n,m = map(int,input().split())
ball = list(map(int,input().split()))
result = 0
# 1부터 10까지의 무게
array = [0] * 11

# 무게별로 카운팅
for i in ball:
    array[i] += 1

# 경우의 수
for i in range(1,m+1):
    # a가 선택했던 볼링공 제거
    n -= array[i]
    result += array[i] * n

print(result)

출저

이것이 취업을 위한 코딩 테스트다 with 파이썬
저자 : 나동빈