[python3] 이코테 - 볼링공 고르기 (ch.11 그리디 - 유형별 기출문제)

참고) 이것이 취업을 위한 코딩테스트다 with 파이썬 책을 기반으로 작성된 문제와 코드입니다. 
따라서 문제는 자세하게 적지 않고, 간단한 설명과 제 코드만 올리겠습니다.

 

볼링공 고르기 (ebook 기준 p.515)

- A.B 두사람 볼링치는 중
- 서로 무게가 다른 볼링공을 고르려고 한다.
- 볼링공 갯수 N개
- 공마다 무게가 적혀있고, 공의 번호는 1번부터 순서대로 부여됨.
- 볼링공의 무게는 1부터 M 사이의 자연수
- N이 5이고, M이 3이면 1,3,2,3,2 무게의 공이 존재. 각 공은 1번~5번이겟지?
- 두 사람이 고를 수 있는 볼링공의 번호 조합의 경우의 수를 구하시오.

##### 입력조건
1. 첫쩃줄 N 과 M이 주어짐
2. 1 <= N <= 1000, 1<= M <= 10
3. 둘쩃줄 각 공의 무게 K (1 <= K <= M)

 

<1. 첫번째 시도 - 나의 코드 : 맞은 코드> 

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

import itertools 

def solution(n, m, ball_weight):
    count = 0
    ABlist = list(itertools.product((ball_weight),repeat = 2))
    
    for i in range(len(ABlist)):
        x, y = ABlist[i]
        if x != y:
            count+=1
    return count//2

solution(n, m, ball_weight)

 

<2. 정답코드 보고 수정해본 코드>

• 느낀점
  • 나는 그리디에 대한 이해가 부족한 것같다.
  • 책의 풀이는 하나를 선택하고, 그게 최고(혹은 최소)가 되는 것을 찾아나가는 탐욕의 방식으로 푸는 방면에, 나는 모든 문제를 경우의 수나, 탐색하는 느낌으로 문제를 구현해나가고 있다. 그리디에 대한 연습이 더 필요할 것같다.

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

def solution(n,m, ball):
    # n: 공의 개수 m: 공의 무게는 m이하
    # 핵심1: A/B는 같은 무게의 공을 사용하면 안돼
    # 핵심2: 하지만 같은 무게의 공일지라도 번호가 달라서 다른 경우로 취급
    
    # 1. 같은 무게가 몇개 씩 존재하는지 확인
    ball_count = [0] * (m+1) # 어차피 무게m이하의 공만 존재
    for b in ball:
        ball_count[b] += 1
    
    result = 0
    # 2. 공을 선택할 수 있는 경우의 수 계산
    for i in range(1, m+1):
        # i = 무게 1, 무게2.... A가 선택하는 공의 무게라고 치자.
        # ball_count[1] 은 무게1인 공을 선택하는 A의 경우의수 
        a = ball_count[i]
        # 중복이 되지 않게 앞서 계산한 수는 삭제되어야 하기 때문에 전체 n 개에서 A가 선택한 공의 개수를 뺀다.
        n -= a
        # b 가 가질 수 있는 경우의 수는, a가 공을 가져간 나머지 n 가지 이다.
        result += a*n
    return result

solution(n, m, ball)