programmers- lv.2 (귤 고르기)

문제링크: 귤 고르기

✍🏻 Information

	content
언어	python
난이도	⭐️⭐️⭐️
풀이시간	52분
제출횟수	∞
인터넷검색유무	yes

🍒 My Code

import collections
def solution(k, tangerine):
    counter = collections.Counter(tangerine)
    c = sorted(counter.values(),reverse=True) 
    #binary search
    start,end =0, len(tangerine) - 1
    while start <= end:
        mid = (start + end) // 2
        SUM = sum(c[:mid+1])
        if SUM >=k:
            if sum(c[:mid])<k:
                return mid+1
            else:
                end = mid -1
        elif SUM < k:
            start = mid + 1

💡 What I learned

• 시간초과에 굉장히 시달렸다. 아래와 같이 여러방법을 해보았지만.. 이 문제는 binary search 없으면 안되는것 같다.

	#풀이1
	tangerine.sort()
    num = []
    for i in range(1,len(tangerine)):
        if tangerine[i-1]!=tangerine[i]:
            num.append(i-sum(num))
    num.append(len(tangerine)-sum(num))
    num.sort(reverse=False)
    
    #풀이2
    counter = collections.Counter(tangerine)
    n = 1    
    while 1:
        if sum([i[1] for i in counter.most_common(n)])>=k:
            return n
        n+=1
	
    #풀이3
    answer = 0
    num = {}
    for i in range(min(tangerine),max(tangerine)+1):
        num[i]=tangerine.count(i)
    num.sort(reverse=True)
    for i in num:
        k-=i
        answer+=1
        if k<=0:
            break
    return answer

• 리스트에서 빈도수가 가장 높은 요소 출력: max(data, key=data.count)
• binary search: 시간복잡도 O(logN)

  target : 찾고자 하는 값
  data : 오름차순으로 정렬된 list
  start : data 의 처음 값 인덱스
  end : data 의 마지막 값 인덱스
  mid : start, end 의 중간 인덱스

def binary_search(target, data):
    data.sort()
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return mid # 함수를 끝내버린다.
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None #data 중 target이 있으면 index 값을 return, 없으면 None을 return

• 다른 사람 풀이

import collections
def solution(k, tangerine):
    answer = 0
    cnt = collections.Counter(tangerine)

    for v in sorted(cnt.values(), reverse = True):
        k -= v
        answer += 1
        if k <= 0:
            break
    return answer

-> 나처럼 sum으로 안구하고 빼는 방식으로 했으면 시간초과 안걸리나보다.

-> count는 시간을 굉장히 많이 잡아먹지만 counter는 괜찮다고 한다(응정)
-> 파이썬에서 시간초과 나면 딕셔너리가 좋다고 한다(응정)