[Python]Programmers 귤 고르기(lv2) - Counter

1. 문제

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/138476

프로그래머스

 

각 귤의 크기가 담겨있는 배열에서 k 개의 귤을 선택할 때 

 

서로 다른 크기의 귤을 최소한으로 선택하는 방법을 구하는 문제이다.

 

각 귤의 크기가 담겨있는 배열이 주어지면 서로 다른 크기의 수의 최소값을 출력하면 된다.

 

2. 풀이

무난하게 풀었다고 생각했는데 역시나 시간초과가 발생했다.

 

반복문을 통해 주어진 배열을 돌면서 chks(중복을 검사하는데 사용할 배열)에 있으면 넘어가고

 

chks에 없다면 chks에 해당 원소를 chks에 추가하고(다음에 같은 사이즈가 나왔을때 한번 더 보지 않기 위함) 리스트의 .count() 메서드를 통해서 해당 사이즈의 개수를 sizes 배열에 추가해준다.

 

이렇게 하면 어떤 크기인지는 모르지만 같은 크기의 귤이 몇개 있는지는 파악할 수 있다. 

 

.sort(reverse=true) 메서드를 통해서 내림차순으로 정렬해주고

 

많은 것부터 k가 될때까지 카운트 해주면 원하는 값을 구할 수 있었다.

 

count() 메소드는 리스트를 다 검색하는 절차가 필요하기에 시간복잡도가 O(n)이다.

 

리스트의 범위가 아주 넓기 때문에 이 부분에서 시간 초과가 발생한 것 같다.

 

도저히 시간 초과를 해결할 수 있는 방법을 찾지 못해 다른분들의 코드를 참고하였는데 대부분 Counter를 이용하셨다.

 

Counter를 이용한 풀이과정은 다음과 같다.

 

1. Counter를 이용하여 같은 크기가 몇번 중복되었는지 확인한다.

2. most_common을 이용하여 최빈값 순서로 정렬한다.

3.그 후 value 값(temp[1]) 을 더해주면서 k보다 크거나 같을 때 몇 종류의 귤이 담겼는지를 리턴해준다.

 

Counter()는 귤 크기에 해당하는 귤의 개수를 딕셔너리 자료구조로 반환해준다.

 

3. 코드

시간초과가 발생하는 코드:

def solution(k, tangerine):

    answer = 0

    sizes = []

    chks = []

    tangerine.sort()

   

    for gyul in tangerine:

        if gyul not in chks:

            chks.append(gyul)

            cnt = tangerine.count(gyul)

            sizes.append(cnt)

        else:

            continue

       

    sizes.sort(reverse=True)

   

    j=0

    for cnt in sizes:

        answer += 1

        j += cnt

        if j >= k:

            return answer

       

 

정답 코드:

from collections import Counter

def solution(k, tangerine):

    answer = 0

   

    cnts = Counter(tangerine)

    cnts = cnts.most_common()

   

    j=0

    for cnt in cnts:

        answer += 1

        j += cnt[1]

        if j >= k:

            return answer