볼링공 고르기 [그리디]

# 서로 무게가 다른 볼링공을 고르려고 함
# 볼링공 N개, 무게가 적혀있음
# 볼링공 무게는 1~M까지 자연수 형태
# 볼링공 번호의 조합을 구하시오.


n,m=map(int,input().split())
array=list(map(int,input().split()))
count=0

# 볼링공을 리스트로 만들어 탐색하고 같은 무게인지 체크하기

for i in range(len(array)-1):
    for j in range(i+1,len(array)):
        if array[i]==array[j]:
            continue
        else:
            count+=1

print(count)
            

• 볼링공을 리스트로 만들고 i 번째 볼링공을 i+1번째부터 n(=len(array))번째 볼링공과 비교 후 무게가 다른 것만 추출

좋은 풀이

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

# 1부터 10까지 무게를 담을 수 있는 리스트
array=[0]*11

for x in data:
    #각 무게에 해당하는 볼링공 개수 카운트
    array[x]+=1

result=0

# 1부터 m까지의 각 무게에 대해 처리

for i in range(1,m+1): # 무게 탐색
    n-=array[i] # A가 B보다 먼저 선택할 수 있는 무게가 i인 볼링공 개수 제외
                # 서로 무게가 달라야 하기 때문
    result+=array[i]*n # B가 무게 i인 볼링공을 선택하는 경우의 수와 곱하기

print(result)

• 볼링공의 무게가 1~10까지이기 때문에 이를 리스트로 만들어서 A가 먼저 선택하고, 나머지를 B가 선택하는 식으로 풀 수 있다
• 시간이 훨씬 단축되는 풀이.