[프로그래머스] Lv.2 귤 고르기 | Python

 

프로그래머스 - 코딩테스트 연습 - 귤 고르기(138476)

프로그래머스

---

Lv2. 귤 고르기 (파이썬 문제 풀이)

---

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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

---

오답 풀이 (시간초과)

#138476 귤고르기

def solution(k, tangerine):
    answer = 0
    ###1###
    
    typeOfTangerine = list(set(tangerine))
    typeNumber = {}
    
    ###2###
    
    for i in typeOfTangerine:
        typeNumber[i] = tangerine.count(i)

    ###3###
    sortedTypeNumber = sorted(typeNumber.items(), key=lambda x: x[1], reverse=True)
    for i in range(len(sortedTypeNumber)):
        k -= sortedTypeNumber[i][1]
        answer += 1
        if k >= 0:
            break

    return answer

첫 풀이에서 시간 초과가 났다.

이에 대해서 확인을 해보니 리스트에서 i 원소를 찾는 count() 함수는 리스트를 다 검색하는 절차가 필요하기에 시간복잡도가 O(n)이다.

따라서, for문을 돌면서 count를 하는 것이 시간초과가 나온 원인으로 보인다.

그렇기에 주석으로 2번 코드블록 - `typeNumber` 딕셔너리에 요소를 추가하는 부분 - 을 아래와 같이 변경해 주었다.

    for i in tangerine:
        if i in typeNumber:
            typeNumber[i] += 1
        else:
            typeNumber[i] = 1

count 함수를 사용하는 대신 직접 for문을 통해 key에 맞는 value값을 1씩 추가하는 방식으로 대신했다.

 

정답풀이

#138476 귤고르기

def solution(k, tangerine):
    answer = 0
    
    ###1###
#    typeOfTangerine = list(set(tangerine))
    typeNumber = {}
    
    ###2###
    for i in tangerine:
        if i in typeNumber:
            typeNumber[i] += 1
        else:
            typeNumber[i] = 1

    ###3###
    sortedTypeNumber = sorted(typeNumber.items(), key=lambda x: x[1], reverse=True)
    
    for i in range(len(sortedTypeNumber)):
        k -= sortedTypeNumber[i][1]
        answer += 1
        if k >= 0:
            break

    return answer

 

풀이과정

주석으로 ###번호###을 한 블록이라고 생각하고 보고자 한다.

1번 블록

주석처리된 부분은 Tangerine의 종류를 set()을 이용해 중복을 제거 후 다시 list로 만들어서 요소를 count 하기 위해 쓴 코드이다. 하지만 이는 for문으로 tangerine요소를 count 하는 방식으로 변하면서 필요가 없어져 주석처리했다. 

typeNumber라는 딕셔너리를 만들어서 type-count를 묶었다.

2번 블록

시간 초과가 나지 않게 typeNumber딕셔너리에 type-count를 넣는 과정

3번 블록

딕셔너리를 value(종류에 따른 개수)에 따라 내림차순으로 정렬했습니다. 이때 sorted를 이용하면 튜플리스트로 반환된다

그다음 value가 많은 순대로 주어진 귤 k개에 할당했다.

---

개인적 깨달음

 

1. 딕셔너리를 정렬하는 것은 자주 사용해보지 않아서 헤맸습니다. lambda를 통해 key순서로 정렬할 건지, value순서로 정렬할 건지 선택할 수 있음을 배웠습니다.

2. 쉽게 count() 함수를 사용하려고 했는데 시간복잡도를 고려해야 하는 점을 다시 생각해 보게 되었습니다.

3. 마지막 if문에서 `k==0`으로 조건을 줬었는데 그렇게 하면 음수(마이너스)가 되는 상황이 고려 안된다는 사실을 테스트를 통해 깨닫고 조건을 변경하였습니다.