프로그래머스-귤고르기(Python)

1. 첫 풀이 

def solution(k, tangerine):
    erasedual = list(set(tangerine))
    countarr = []
    answer = 0
 
    for i in erasedual: #시간복잡도 n제곱 여기서 줄여야겟네?
        a = tangerine.count(i)
        countarr.append(a)
    countarr.sort(reverse=True) #시간복잡도 nlogn
    for j in countarr:
        k -= j
        answer=1
        if(k<=0):
            break
    return answer

귤의 크기가 최소가 되도록 골라야한다. 그래서 나는 귤이 담겨져있는 tagerine을 먼저 중복을 제거해주었다. 왜냐면 각각의 크기들을 count해주어서 정리를 하려 했는데 겹치는 것들은 해줄 필요가 없기 때문이다. 그 후 for문을 돌면서 각각의 원래의 tangerine에서 개수를 세주어 countarr에 넣어준후 많은것순으로 앞에서부터 정렬해주었다. 그 이유가 많은것들을 위주로 뽑으면 종류를 최소화 할수 있기 때문이다. 그후 k에서 빼주며 k가 0이하가 되면 끝났기에 break걸어주었다.

하지만 결과는 시간초과

아마 count도 시간복잡도가 n이고 for문도 n이기에 n제곱의 시간복잡도가 나왔기때문이다. 

---

2트 시작갑니다. 시간복잡도를 줄이기 위해 count를 손봐야한다고 생각하였다. 그래서 생각한것이 현재는 오로지 배열로 문제를 해결하였지만 딕셔너리로 만든후 value에다가 개수를 넣고 그에 따라 정렬을 한다면 시간복잡도가 nlogn이기에 할수 있다고 생각했다.

def solution(k, tangerine):
    a = {}
    answer = 0
    for i in tangerine: 
        if i in a:
            a[i] += 1
        else:
            a[i] = 1
    a = dict(sorted(a.items(), key=lambda x: x[1], reverse=True))
    for j in a:
        k -= a[j]
        answer+=1
        if(k<=0):
            break
    return answer

역시 성공!!!