이코테 | 볼링공 고르기

💻이코테 | 볼링공 고르기

 

** 교재에 첨부된 문제라 문제는 작성하지 않습니다

 

쉬운 그리디 문제였지만, 내 풀이와 교재의 풀이가 달라서 정리해보려구 한다!

 

✏️ 내 풀이

N, M = map(int, input().split())
data = list(map(int, input().split()))

result = 0

for i in range(N):
    for j in range(i+1, N):
        if data[i] != data[j]:
            result += 1

print(result)

 

난 간단하게 반복을 하며, 중복 제거를 위해 j의 범위를 i+1 부터 N 까지 잡아주고 같은 무게가 아닐 때, result 값에 +1 해주었다.

 

📙교재 풀이

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

array = [0] * 11
for x in data:
    array[x] += 1

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

print(result)

 

교재의 경우 경우의 수를 생각하였다.

먼저 무게마다 불링공이 몇 개 있는지를 계산한 후, A가 특정한 무개의 볼링공을 선택했을 때, 이어서 B가 볼링공을 선택하는 경우를 차례대로 계산을 하였다. 

 

---

🤔 내생각

내 풀이가 훨씬 직관적이고 간단한 것 같은 느낌이 들지만, 시간 복잡도를 따져보면 교재의 풀이가 더 작으니까 교재의 식으로도 풀어보고 이해해보았다!