[이코테] CH03 그리디 실전문제 5번 볼링공 고르기

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
INF = 1e9


N,M = map(int,sys.stdin.readline().split())
x = list(map(int,sys.stdin.readline().split()))
x.sort()
count = 0 
for i in range(len(x)):
    for j in range(i,len(x)):
         if x[i]!=x[j]:
              count +=1

print(count)

처음에 보고

이렇게 쉽다고? 하면서 풀었는데

이러면 반복문이 총

len(x) * ( 1 + 2 + ... (len(x)-1)만큼 돌아가므로 

메모리를 효율적으로 관리하고자 하면 다른 풀이를 찾는게 좋아보인다.

메모리 제한이 128MB라서 걸리진 않을 것 같지만

이왕이면 효율적인 풀이로 푸는 것이 시간 초과를 가져오지 않을 것

import sys
# sys.stdin.readline()
from collections import deque
sys.setrecursionlimit(100000000)
import heapq
INF = 1e9


array = [0] * 11 # 범위가 0부터 10까지밖에 없으므로 계수정렬로 효율적이게 관리 가능
N,M = map(int,sys.stdin.readline().split())
x = list(map(int,sys.stdin.readline().split()))
for i in x:
    array[i] +=1

count = 0
for i in range(1,M+1):
    N = N - array[i] # 자기 자신과 무게가 같은 것들을 제외시켜준다. 
    count += array[i] * N # 자기 자신을 제외하고 선택할 수 있는 것은 전체의 경우에서 array[i]를 제외한 것이므로 N을 곱해준다.

print(count)

이런 효율적인 방법도 있다

아래꺼가 훨씬 좋으니..아래 풀이를 좀더 떠올리도록 하자