[level 2] 귤 고르기

문제

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

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

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

 

 

---

 

 

 

문제 풀이 접근법1

1) 귤의 개수만큼 0으로 초기화한 리스트 num, 골라진 귤의 무게를 담을 리스트 size를 선언한다.

2) tangerine의 원소로 반복문을 돌면서 무게에 해당하는 귤의 개수를 배열로 선언한다. (귤의 무게: index, 해당 무게의 귤의 개수: 원소)

3) 반복문을 돌면서 만약 answer가 k보다 같지 않고, 작으면 1이상의 값인 i를 확인하고 i를 size 리스트에 넣고, answer에 i번째 원소를 추가한다.

4) size의 길이를 반환한다. 

def solution(k, tangerine):
    num = [0 for i in range(len(tangerine))]
    size = []
    answer = 0

    for i in tangerine:
        num[i] +=1

    num.sort(reverse=True)

    for i in range(len(num)):

        if answer != k and answer < k:
            answer+=num[i]
            size.append(i)
        
    return len(size)

문제가 워낙 많으므로 따로 얘기하지 않겠습니다..

당근 샘플 테스트 케이스의 마지막을 통과하지 못함 

 

 

문제 풀이 접근법2

1) tangerine의 무게를 key값으로, 개수를 value로 하는 딕셔너리 num을 정의한다.

2) 딕셔너리의 vlaue값을 기준으로 내림차순 정렬한다.

3) 딕셔너리의 value를 기준으로 for문을 돌리면서 딕셔너리의 value만큼 이중 반복문을 구현, size의 길이가 k와 같지 않다면 i(딕셔너리의 key, 귤의 무게)를 size에 추가한다. 만약 size와 길이가 같다면 break로 나온다. 

4) size를 set으로 변경 한 후, 세트의 길이를 반환한다. 

def solution(k, tangerine):
    num = {}
    size = []

    for i in tangerine:
        if i not in list(num):
            num[i] = 1
        else:
            num[i] +=1

    num = sorted(num.items(), key=lambda x:x[1], reverse=True)

    for i, j in num:
        for z in range(j):
            if len(size) != k:
                size.append(i)
            else:
                break
        
    return len(set(size))

테스트 케이스 27~30, 테스트 케이스 33~34번에서 시간 초과로 실패했다. 

 

 

문제 풀이 접근법3

1) tangerine의 무게를 key값으로, 개수를 value로 하는 딕셔너리 num을 정의한다.

2) 딕셔너리의 vlaue값을 기준으로 내림차순 정렬한다.

3) 딕셔너리의 key를 i, value를 j로 받아 반복문을 진행한다. 만약 size가 k보다 크거나 같다면 반복문을 탈출하고, 그게 아니라면 answer에 1을 추가하고, size에 j를 추가한다. 

4) answer를 반환한다. 

def solution(k, tangerine):
    num = {}
    size, answer = 0, 0

    for i in tangerine:
        if i not in list(num):
            num[i] = 1
        else:
            num[i] +=1

    num = sorted(num.items(), key=lambda x:x[1], reverse=True)

    for i, j in num:
        if size >= k:
            break
        answer +=1
        size += j
        
    return answer

역시나... 테스트 케이스 27~30, 테스트 케이스 33~34번에서 시간 초과로 실패했다. 

아니 근데 진짜 왜 인지 ㅁ모르겠음

다른 분들 코드랑 다른 것 같지 않은데...??? 물론 내가 잘못 이해하고 있어서 그렇겠지만...

다음번에 다시 try해보겠습니다. 

 

문제 풀이 접근법4

not in에서 시간초과가 발생하는 것 같다는 피드백을 받고 num 딕셔너리를 Counter를 사용하여 생성하였다. 

from collections import Counter
def solution(k, tangerine):
    num = {}
    size, answer = 0, 0

    num = Counter(tangerine)

    num = sorted(num.items(), key=lambda x:x[1], reverse=True)

    for i, j in num:
        if size >= k:
            break
        answer +=1
        size += j
        
    return answer

 

 

---

 

✏️ 오늘의 배운 점 

in, not in은 시간복잡도가 각각

list: O(n)

set, dictionary: O(1) ~ O(n)

이다.

출처: https://twpower.github.io/120-python-in-operator-time-complexity

[Python] 파이썬 'in' 연산자 시간 복잡도(Time Complexity)

 

세상에...자료구조 공부 열심히 안한 업보를 이렇게...맞다니...

진짜 과거로 돌아간다면 나에게 해주고 싶은말..

자구 열심히 들어라.. 방학하면 진짜 복습한다....