알고리즘 문제
시도
수확한 귤 중에서 판매를 위해 고르는 개수는 k, 수확한 귤의 크기는 array에 담겨져 입력된다.
k개를 판매할 때 크기가 서로 다른 종류의 수의 최솟값을 return 해야 한다는 말은 동일한 크기의 갯수가 가장 많은 순서대로 담으면 크기의 종류가 최소가 될 것이다.
코드를 작성하기 전에 생각 해 봤다.
1. array에 입력되는 크기는 무작위로 들어오기 때문에 입력받은 array의 요소들의 개수를 먼저 세어준다
2. 크기가 가장 많은 것 순서대로 k개 까지만 담을 것이다.
3. 총 개수에서 k개 만큼이 담기고나면 최소가 되는 종류의 수를 return한다.
해결
위 과정대로 내가 작성한 답안은 다음과 같다.
def solution(k, tangerine):
keys = set(tangerine)
dic = {}
for key in keys:
dic[key] = 0
for a in tangerine:
if a in dic:
dic[a] += 1
an_dic = dict(sorted(dic.items(), key=lambda x: x[1], reverse=True))
num = 0
for i, temp in enumerate(an_dic):
num += an_dic[temp]
if num >= k:
return i+1각 크기별 개수를 파악할 수 있도록 크기(key): 개수(value)쌍으로 dictionary를 만들어 줬다.
- array 입력값이 무작위로 들어오고 key값은 중복되지 않아야 하기 때문에 set함수를 사용해서 중복값을 제거 해 줬다.
- 빈 dic를 만들고 각 key의 value를 0으로 설정 후 array를 돌면서 value를 1씩 더해줬다.
만들어진 dic을 value값을 기준으로 내림차순으로 정렬 후 최소값 도출 과정을 작성했다.
- 상자에 담겨진 현재 귤을 나타내는 num=0을 설정
- 정렬된 an_dic에서 가장 많은 갯수를 가진 크기를 먼저 담아준 후 담겨진 개수가 k보다 작으면 다음 크기를 담을 수 있도록 for문을 작성했다.
- an_dic의 key를 기준으로 돌면서 num의 값이 k값 이상이 됐을때 멈추고 그때 담겨진 크기의 종류 수를 알 수 있도록 enumerate를 사용했다.
- i의 값은 0부터 시작하기 때문에 num >= k가 됐을때의 i값에 +1 값이 크기의 종류가 최소일때 그 종류의 수가 될 것이다.
고찰
처음 막막했던 부분이 array의 값을 어떤식으로 저장을 해야하는가에 대한 것이었다. 풀이과정이 머리속에 그려지지만 주어진 데이터들을 어떻게 활용할 것인지에 대한 경험이 아직 부족한 것 같다. 지금 생각해보면 dictionary가 바로 떠오르지만 처음 마주했을때 dictionary를 생각하기까지 시간이 오래걸렸었다. 알고리즘에 조금 더 시간을 투자해서 극복해야될 것 같다.
Counter
하나하나 내가 알고있는것들을 사용해서 구현을 하는 과정에서 더 효율적이거나 줄일 수 있는 방향도 알아봤다. 다른사람의 풀이방식도 참고해봤을때 파이썬 내장함수인 Counter라는 것이 있었다.
-
입력된 데이터의 값을 중복에 따라 key:value값으로 반환해주는 함수
-
사용하기 위해서 파이썬의 collections모듈의 Counter클래스를 import해줘야 한다.
from collections import Counter- 무작위 리스트에 적용하게 되면 하나의 요소(key)마다 중복되는 개수(value)를 반환, value값이 높은 순서대로 나열된다.
a_list = ['a', 'c', 'b', 'b', 'a', 'c', 'b', 'c', 'c']
cnt_a = Counter(a_list)
print(cnt_a)
Counter({'c': 4, 'b': 3, 'a': 2})- 문자열에 적용하게 되면 각 문자(key)마다 문자열에서 중복되는 개수(value)를 반환, value값이 높은 순서대로 나열된다.
a = 'hello world'
cnt_a = Counter(a)
print(cnt_a)
Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})해당 Counter함수를 적용하면 아래와 같이 작성 할 수 있다.
from collections import Counter
def solution(k, tangerine):
dic = Counter(tangerine)
num = 0
for i, temp in enumerate(dict(sorted(dic.items(), key=lambda x: x[1], reverse=True))):
num += dic[temp]
if num >= k:
return i+1