Programmers - 귤 고르기
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제
경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.
예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.
경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.
접근방식
먼저 tangerine 배열의 길이를 구해주고 set으로 감싼 배열을 돌면서 각 원소가 몇 개 나오는지 target_arr에 할당해줌
만약 target_arr의 가장 큰 값이 k보다 크거나 같으면(가장 중복이 많은 값이 판매하려는 귤의 개수보다 크거나 같으면) 해당 과일만 판매하면 되기 때문에 answer = 1 로 할당해줌
만약 아니면 target_arr 를 내림차순으로 정렬하고 tmp 라는 변수를 0으로 생성하고 target_arr 를 돌면서 tmp 변수에 값을 더해주면서 answer도 1씩 더해줌. 그리고 tmp가 k보다 크거나 같아질 때 반복문을 탈출하고 answer 를 반환해줌
이렇게 푸니,
다음과 같이 시간초과가 떴음.
배열을 돌면서 count() 를 사용했는데 이는 리스트를 통째로 훑어야해서 시간이 오래걸려서 시간 초과가 뜰 수 밖에 없었음
이 대신 각 요소의 개수를 더 효율적으로 계산할 수 있는 방법을 생각해보았음
딕셔너리를 사용해서 먼저, 각 요소의 개수들을 구하는 방법으로 구현하니, 시간 초과 없이 문제를 풀 수 있었음
기존 코드
def solution(k, tangerine):
total_count = len(tangerine)
target_arr = []
answer = 0
for t in set(tangerine):
target_count = tangerine.count(t)
target_arr.append(target_count)
if max(target_arr) >= k:
answer = 1
else:
target_arr.sort(reverse=True)
tmp = 0
for t in target_arr:
tmp += t
answer += 1
if tmp >= k:
break
return answer
수정 코드
def solution(k, tangerine):
answer = 0
tmp = 0
target_dict = {}
for t in tangerine:
target_dict[t] = target_dict.get(t,0) + 1
target_arr = sorted(target_dict.values(), reverse=True)
for t in target_arr:
tmp += t
answer += 1
if tmp >= k:
break
return 1 if max(target_arr) >= k else answer
cf) dict의 get() 이란?
count_dict[t] = count_dict.get(t, 0) + 1 부분은 딕셔너리에서 특정 키 t에 대한 값을 가져옴.
get() 메서드는 주어진 키에 대한 값을 반환하며, 해당 키가 없으면 기본값으로 지정된 값(0)을 반환함.
그 다음 해당 키 t에 대한 값을 1 증가 시킴. 이를 통해 count_dict에 각 요소의 등장 횟수를 구할 수 있음
해당 방법으로 푸니 속도가 눈에 띄게 빨라졌음을 알 수 있음