Chapter 11-5 볼링공 고르기

<무지성 코드>

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

for i in range(len(l)-1):
    for j in range(i+1, len(l)):
        if l[i] != j:
            count += 1

print(count)

 

<답안 예시>

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)

 

나의 풀이는 볼링공의 무게가 중복되지 않으면 count를 1씩 증가시키는 방법으로 풀었다. 구현하기는 쉬웠지만 이중 반복문을 사용해 시간복잡도면에서는 확실히 답안 예시가 더 효과적이었다.

답안에서는 볼링공의 무게가 1~10으로 제한된 점을 기억해 관련된 배열을 만들고 반복문 하나를 이용해 반복할 때마다 해당 무게에 이미 계산했던 무게를 제외해가면서 곱했다. 공간복잡도와 시간복잡도의 관계를 생각해보니 계수 정렬과 비슷한 느낌이 있다.