[이코테,python] 볼링공 고르기

---

처음엔 그냥 무지성으로 이중 포문으로 풀었다.

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

# sol1) n^2
lst = []

cnt = 0
for i in range(n):
    lst.append(weight[i])

for i in range(n - 1):
    for j in range(i + 1, n):
        if lst[i] != lst[j]:
            cnt += 1
print(cnt)

 

풀고나서 다른사람들의 풀이를 보았는데, 이런 문제의 경우에 수학적 사고를 통해서 시간 복잡도를 n으로 줄일수 있는것을 알게 되었다.

n, m = map(int, input().split())
weights = list(map(int, input().split()))
# value를 가진 경우의 수
lst = [0] * m
result = 0
for i in weights:
    lst[i - 1] += 1
print(lst)
for i in range(m):
    print('lst[i]: ',lst[i])
    n -= lst[i]  # a를 고르고
    print('n: ', n)
    result += lst[i] * n  # b를 골라
    print('after: ',result)

print(result)

 

어렵거나 그런 문제는 아니었는데, 발상의 전환이 기록해 놓을만한 가치가 있을것 같아서 글로 남겨보았다.