- 귤 고르기
문제 설명
경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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 |
| 4 | [1, 3, 2, 5, 4, 5, 2, 3] | 2 |
| 2 | [1, 1, 1, 1, 2, 2, 2, 3] | 1 |
입출력 예 설명
입출력 예 #1
- 본문에서 설명한 예시입니다.
입출력 예 #2
- 경화는 크기가 2인 귤 2개와 3인 귤 2개 또는 2인 귤 2개와 5인 귤 2개 또는 3인 귤 2개와 5인 귤 2개로 귤을 판매할 수 있습니다. 이때의 크기 종류는 2가지로 이 값이 최소가 됩니다.
입출력 예 #3
- 경화는 크기가 1인 귤 2개를 판매하거나 2인 귤 2개를 판매할 수 있습니다. 이때의 크기 종류는 1가지로, 이 값이 최소가 됩니다.
def solution(k, tangerine):
tmp_list = []
# 처음 풀이를 냈을 때는 list.count() 를 이용하여 이중 for문을 사용하였다. 하지만 O(n2)의 시간이 걸려서 이를 취소하고 직접 해당 count를 구현하여 시간초과를 없앨 수 있었다.
# check_list = list(set(tangerine))
# for i in range(len(check_list)):
# # cnt = 0
# # for j in range(len(tangerine)):
# # if check_list[i] == tangerine[j]:
# # cnt += 1
# cnt = tangerine.count(check_list[i])
# tmp_list.append([check_list[i], cnt])
# tmp_list.sort(key = lambda x:-x[1] )
# 리스트 처리를 위해 sort()를 활용하여 같은 숫자끼리 붙어있게 처리
tangerine.sort()
# 초기 카운트 (중복 개수 세기)
cnt = 1
for i in range(len(tangerine)):
# 마지막 숫자일 경우 현재까지 cnt 개수와 마지막 숫자 저장
if i == len(tangerine) - 1:
tmp_list.append([tangerine[i], cnt])
# 리스트 다음 인덱스 숫자와 비교하여 같으면 cnt 숫자 증가
elif tangerine[i] == tangerine[i + 1]:
cnt += 1
# 다를 경우 현재까지 cnt와 해당 숫자 저장
else :
tmp_list.append([tangerine[i], cnt])
cnt = 1
# if tangerine[-1] == tmp_list[-1][0]:
# tmp_list[-1][0] += 1
# else :
# tmp_list.append([tangerine[-1], tangerine.count(tangerine[-1])])
# 저장된 리스트에서 카운트 크기순으로 정렬
tmp_list.sort(key = lambda x:-x[1])
total = 0
result = 0
# 카운트 크기순으로 더하고 만약 그 크기가 k를 넘어갈 경우 break하고 결과 출력
for info in tmp_list:
total += info[1]
result += 1
if k <= total :
break
answer = result
return answer배울점
해당 문제를 풀면서 두 가지 method 를 다시금 기억에서 꺼내서 사용하였다. 처음은 .count() 로 리스트에서 중복된 개수를 출력해주는 method인데 사용했을 당시 이중 for문으로 풀어야 해서 자꾸 시간초과가 발생하였다. 따라서 O(N^2)보다는 O(N)으로 풀이하기 위해 직접 중복 개수를 체크하는 방법을 사용하였다.
파이썬 리스트의 특정 요소 개수 구하기 → count()사용
i = [1,1,3,4,5,3,3,7,6,8,9,3,2,5,9]
print(i.count(3)) #리스트i에 요소3의 개수 구할때
>>> 4 다음으로는 sort()안에 기준을 설정하여 정렬하는 방법이다. 예전에 몇번 사용하였는데 생각 외로 기억이 안나서 찾아본다음 사용하였다.
sorted()
Prototype
sorted( <list> , key = <function> , reverse = <bool>)
# <list> 뿐 아니라, <Tuple>, <Dictionary>, <Str>에도 사용 가능하다.- 원본 내용을 바꾸지 않고, 정렬한 값을 반환한다.
- List, tuple, Dictionary, str에 모두 사용 가능하다.
key를 통하여 정렬할 기준을 정할 수 있다.reverse가 True이면 내림차순, False이면 오름차순으로 정렬된다.
arr = [10, 40, 20, 15]
arr = sorted(arr, reverse = True)
print(arr)
>>>> [40, 20, 15, 10]sort()
Prototype
<list>.sort(key = <function>, reverse = <bool>)- 원본 자체를 수정한다.
- 반환값은 None
- Tuple , Dictionary, Str 에는 사용이 불가하다.
key값을 사용하면 여러가지 기준으로 정렬을 실행할 수 있다.
2중 리스트에서 정렬하기
array = [[50, "apple"], [30, "banana"] , [400, "melon"]]위와 같이 [Int, Str]형식의 요소를 가진 리스트가 존재할때
Int 를 기준으로 정렬하기
.sort() 함수 사용
array.sort(key = lambda x:x[0])
print(array)
>>>>> [[30, 'banana'], [50, 'apple'], [400, 'melon']]sorted() 함수 사용
print(sorted(array, key = lambda x: x[0]))
>>>>> [[30, 'banana'], [50, 'apple'], [400, 'melon']]Str을 기준으로 정렬하기
Sort() 함수 사용
array.sort(key = lambda x:x[1])
print(array)
>>>>>[[50, 'apple'], [30, 'banana'], [400, 'melon']]sorted() 함수 사용
print(sorted(array, key = lambda x: x[1]))
>>>>>[[50, 'apple'], [30, 'banana'], [400, 'melon']]# key가 여러개 일때 (다중조건 정렬)
array = [("A", 18, 300000) , ("F", 24, 10000), ("T", 24, 200000),("Q",24,5000000), ("B", 70, 5000)]
# (<이름> , <나이> , <재산>) 이라고 하면- 위의 리스트처럼 정렬해야 할때 고려해야 많은 경우가 있을때는 튜플형식으로
key = lambda x: (x[0] , x[2])lambda식을 세워주면 된다. - 그리고 내림차순으로 하고 싶다면 마이너스 부호를 붙여주면 된다. `key= lambda x: (-x[0], x[2])```
