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

lv. 2 단계의 코딩 테스트 연습 문제 중 '귤 고르기'에 대한 풀이를 설명하고 있습니다.

 

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

 

코딩 테스트 연습 문제 풀이

 

1. 원리

2. 코드

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

원리

• 귤이 사이즈 별로 몇 개씩 존재하는 최초에 저장한다.
  • sizes[30] = 2 인 경우, 30 사이즈의 귤이 2개가 존재하는 것이다.
• 이제 sizes 배열의 0 ~ 최대 귤 사이즈인 10000000 까지 탐색을 하며 array에 특정 사이즈의 귤이 몇 개씩 있는지 담는다.
  • 위의 예제를 활용하면 array = [[30, 2]] 와 같이 담긴다.
• 이제 1번째 열을 기준으로 정렬한다.
• 즉, 개수가 많은 사이즈가 앞으로 오도록 내림차순 정렬을 수행한다.
• 정렬된 Array의 앞에서부터 탐색하면서 내가 선택해야 되는 귤의 개수 k가 0이 될 때까지 귤을 고른다.
• 해당 코드는 아래와 같다.

for element in array:
    if k != 0:
        if element[1] <= k:
            k -= element[1]
            answer += 1
        elif element[1] > k:
            answer += 1
            break
    else:
        break

 

• 가장 적은 종류로 k개를 담아야 하므로, 많은 수의 귤을 갖는 사이즈부터 선택하면 된다.
• Array의 첫 번째 원소부터 탐색하는 이유이다.
• i번째에 있는 사이즈의 귤을 선택하는 경우를 생각해보자
  • i번째 원소는 [사이즈, 귤의 개수] 로 구성되어 있다.
  • 이때, 귤의 개수가 내가 선택해야할 k보다 작거나 같다면 해당 사이즈의 귤을 선택하면 된다.
  • 따라서 k에서 해당 사이즈의 귤의 개수 (number(i))를 뺀다.
    • 다음부터는 k - number(i) 의 수 만큼을 더 선택해야한다.
  • 그리고 한 종류의 귤을 선택했으므로, answer를 +1 한다.
  • 만약 귤의 개수가 k보다 크면, 해당 귤을 선택하면 k가 꽉차므로 더 이상 다음 사이즈의 귤을 선택할지 말지 고민할 필요가 없다.
  • 따라서 answer를 +1하고, 순회를 멈춘다.
  • 마찬가지로, k == 0 즉 더 이상 선택할 수 있는 귤이 없을 때에도 순회를 멈춘다.
• 전체 코드는 아래와 같다.

코드

def solution(k, tangerine):
    answer = 0
    sizes = [0 for _ in range(10000000)]

    for t in tangerine:
        sizes[t-1] += 1

    array = []
    for size, n in enumerate(sizes):
        if n > 0:
            array.append([size + 1, n])
    array.sort(key=lambda x: x[1], reverse=True)

    for element in array:
        if k != 0:
            if element[1] <= k:
                k -= element[1]
                answer += 1
            elif element[1] > k:
                answer += 1
                break
        else:
            break
    return answer

 

정답률 70%를 보여주는 만큼 아주 단순한 문제였다.