[64일차][Lv2][프로그래머스][138476]귤 고르기

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

1 ≤ k ≤ tangerine의 길이 ≤ 100,000
1 ≤ tangerine의 원소 ≤ 10,000,000

 

입출력

k	tangerine	result
6	[1, 3, 2, 5, 4, 5, 2, 3]	3
40	[1, 3, 2, 5, 4, 5, 2, 3]	2
2	[1, 1, 1, 1, 2, 2, 2, 3]	1

 

코드 및 설명

def solution(k, tangerine):    
    # 중복이 제거된 배열
    tangerine_duplication_arr = list(set(tangerine))
    # 중복 제거된 배열에서 중복의 개수를 넣기 위한 배열
    tangerine_arr = []
    
    # 중복된 개수 체크하여 tangerine_arr에 넣기
    # for idx in range(len(tangerine_duplication_arr)):
    #    for size in tangerine:
    #        if size == tangerine_duplication_arr[idx]:   
    #            if len(tangerine_arr) < idx+1:
    #               tangerine_arr.append(1)
    #            else:
    #                tangerine_arr[idx] += 1
    #        else:
    #            pass    
    for size in tangerine_duplication_arr:
        tangerine_arr.append(tangerine.count(size))
    
    
    
    # 내림차순으로 정렬
    tangerine_arr.sort(reverse=True)    
    
    # k만큼의 크기보다 크거나 같아질 때까지 반복
    count = 0
    for idx in range(len(tangerine_arr)):        
        if tangerine_arr[idx] >= k:
            return 1
        else:
            if count + (tangerine_arr[idx]) >= k:
                return idx+1
            else:                
                count += tangerine_arr[idx]

일단 위에 코드는 시간초과로 통과가 되지 않는다. 아마 중복제거를 하고 중복된 개수를 체크하는 부분에 count함수가 느려지게 하지 않았나 생각하고 있다. 이 문제는 중복된 개수의 값이 k의 값과 같아지면 결국 서로 다른 최소 종류의 수를 알 수 있게된다.

def solution(k, tangerine):    
    tangerine_arr = list(set(tangerine))
    tangerine_obj = {}
        
    # 중복 개수를 dict 형식으로 저장.
    for size in tangerine:
        if size in tangerine_arr:    
            if size in tangerine_obj.keys():
                tangerine_obj[size] += 1
            else:
                tangerine_obj[size] = 1            
    
    # value로 정렬하고 이걸 가지고, value만 추출
    tangerine_obj_sort = list(dict(sorted(tangerine_obj.items(), key=lambda x:x[1], reverse=True)).values())
           
    # k만큼의 크기보다 크거나 같아질 때까지 반복
    count = 0
    for idx in range(len(tangerine_obj_sort)):        
        if tangerine_obj_sort[idx] >= k:
            return 1
        else:
            if count + (tangerine_obj_sort[idx]) >= k:
                return idx+1
            else:             
                count += tangerine_obj_sort[idx]

이번엔 count함수를 뺴고 dict형식으로 중복값을 구한 다음 value만 추출해서 돌렸는 데 시간초과가 뜬다... 시간은 거의 반절이상 줄였는 데... 27, 28, 29, 30, 33, 34,가 안되네 허허... 원소의 개수가 1000만개까지라 아마 그런 것 같은데...음..... 어디를 손봐야하나..................

 

def solution(k, tangerine):    
    tangerine_arr = list(set(tangerine))
    tangerine_obj = { size: 0 for size in tangerine_arr }
    
    # 중복 개수를 dict 형식으로 저장.
    for size in tangerine: 
        tangerine_obj[size] += 1                    
    
    # value로 정렬하고 이걸 가지고, value만 추출
    tangerine_obj_sort = list(dict(sorted(tangerine_obj.items(), key=lambda x:x[1], reverse=True)).values())
           
    # k만큼의 크기보다 크거나 같아질 때까지 반복
    count = 0
    for idx in range(len(tangerine_obj_sort)):
        if count + tangerine_obj_sort[idx] >= k:
            return idx+1
        else:
            count += tangerine_obj_sort[idx]

역시 카운터에서 dict로 변경하고, if문 차이때문에 속도가 현저하게 느려졌던 거다;; 허허 참... 쉽지않네...

이 문제는 결국 중복값을 찾고 중복값을 오름차순으로 나열해서 k보다 크거나 같아질때의 카운트를 리턴하는 거다. 

복잡하게 생각하지말자!!!!!!!!!!!!!!!!!!!!! 쉽게 쉽게!!!