[프로그래머스] Level2 : 귤 고르기[Python]

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

프로그래머스

 

풀이 :

1. 그리디 문제로 귤의 크기에 따른 개수를 세어준 후 개수가 많은 것부터 세어주어야한다.

2. 리스트에 담겨있는 귤의 크기를 오름차순 정렬 후 귤의 크기에 따른 개수를 count_list에 저장

3. count_list의 원소들을 내림차순 정렬(개수가 많은 것부터 세어줘야 하므로)

4. k개 만큼 귤의 개수를 세어줌(코드 주석 참고)

 

코드 :

def solution(k, tangerine):
    answer = 0
    count_list = [] # 귤의 크기에 따른 개수를 저장하기 위한 리스트
    count = 1       # 귤의 크기에 따른 개수를 세기위한 변수

    tangerine.sort()
    if len(tangerine) == 1:    
        count_list.append(1)
    else:
        for i in range(1,len(tangerine)):
            if tangerine[i] == tangerine[i-1]:      # 귤의 크기가 같으면 개수 1 증가
                count+=1
            else:
                count_list.append(count)            # 귤의 크기가 다르면 count_list에 현재 귤의 크기에 해당하는 개수를 추가
                count = 1                           # 다시 count 1로 초기화
            if i==len(tangerine)-1:                 # 마지막 원소일 경우 count_list에 현재 귤의 크기에 해당하는 개수를 추가
                count_list.append(count)
    count_list.sort(reverse=True)                   # count_list 내림차순 정렬(개수가 많은거부터 세줘야하므로)

    for i in range(len(count_list)):                
        if k > count_list[i]:
            k -= count_list[i]
            answer+=1
        else:
            answer+=1
            break
    return answer