[이코테] 그리디 - 볼링공 고르기 python

난이도 : ●○○ | 풀이 시간 : 30분 | 시간 제한 : 1초 | 메모리 제한 : 128MB | 기출 : 2019 SW 마에스트로 입력 테스트

 

문제

• A, B 두 사람이 볼링을 치고 있다.
• 볼링공은 총 N개가 있고 각 공의 무게는 1부터 M까지의 자연수이다.
• 같은 무게의 공이 여러 개 있을 수 있지만 서로 다른 공으로 간주한다.
• 공의 번호는 1번부터 순서대로 부여된다.
• 두 사람이 무게가 서로 다른 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하라.

 

입력조건

• 첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 주어진다. (1<=N<=1,000, 1<=M<=10)
• 둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어진다. (1<=K<=M)

출력조건

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

 

입력예시

5 3
1 3 2 3 2

출력예시

8

 

 

아이디어 - O(n^2) 풀이

• 공의 무게를 리스트에 저장한 뒤에, 2차 반복문으로 현재 공의 무게와 그 뒤의 공의 무게가 다를 때마다 카운트를 1 증가시킨다.

 

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

print(cnt)

 

 

아이디어 - O(n) 풀이

• ball 이라는 리스트에 공의 무게들을 입력받는다.
  • ball = [1, 2, 2, 3, 3]
• 어떤 무게의 공이 몇 개씩 있는지 카운트하는 리스트 weight를 생성한다.
  • weight의 크기는 M+1이다
  • ball에 저장된 값을 하나씩 읽으면서 weight 리스트를 업데이트한다.
  • 그렇게 생성된 weight 리스트 

    0	1	2	3
    	1	2	2

  • 무게가 같더라도 다른 공으로 취급하기 때문에 공을 고를 수 있는 경우의 수는
    • A의 무게가 1일 때 : 1(무게가 1인 공의 개수) x 4(B의 무게가 2인 경우 2가지 + B의 무게가 3인 경우 2가지) = 4가지
    • A의 무게가 2일 때 : 2(무게가 2인 공의 개수) x 2(B의 무게가 3인 경우 2가지)  = 4가지
    • A의 무게가 3일 때 : 2(무게가 2인 공의 개수) x 0(이전에 다 선택되었음) = 0가지

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

weight = [0]*(m+1)
result = 0

for ball in balls:
    weight[ball] +=1

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

print(result)

 

기본적으로 주어지는 값들을 최대한 활용하는 식으로 생각하는 게 쉽지가 않다..