문제
귤을 크기별로 분류했을때, 서로 다른 종류의 개수를 최소화 하려 한다.
예로
귤을 8 개 수확했는데, 크기가 [1,3,2,5,4,5,2,3] 이였다.
귤을 6개 판매하고 싶다면, 크기가 1,4인 귤을 제외한 6개를 담으면
귤을 크기는 2,3,5 로 총 3가지가 되며, 이때 서로 다른 종류가 최소다
즉, 중복되는 숫자가 가장 적은 귤을 하나씩 제거하면 되겠다.
상자에 담으려는 귤의 갯수 k
귤의 크기를 담은 배열 tangerline 이 주어질때,
귤 k 개를 고를때, "서로다른 종류의 수의 최솟값"을 return 해보자
예시
k tangerine result
6 [1, 3, 2, 5, 4, 5, 2, 3] 3 // 2,3,5 (1,4가 제일적음)
4 [1, 3, 2, 5, 4, 5, 2, 3] 2 // 5 ,3 ,2 가 두갠대,(1,4가 제일 적음)
2 [1, 1, 1, 1, 2, 2, 2, 3] 1 // 3이 제일 적음 // 3제외
프로세스
1) 각 크기별로 귤을 정리한다. (객체)
2) 크기별 귤의 갯수별로 정리한다.
3) "가장 많은 수"의 "귤 크기의 갯수" 부터 차례대로 더하여 k 이상이 되도록 한다.
4) 몇번 더해야하는지 확인하여, 그 횟수를 빼낸다.
사용
1. reduce => 각 중복되는 귤 크기의 갯수를 더해, 객체형태로 만듬
2. sort => 갯수가 가장 많은 순서대로 정리
내코드
function solution(k, tangerine) {
const X = tangerine.reduce((acc, cur) => ({ // { 귤크기 : 갯수, 귤크기 :갯수 ... } 형태로 갯수계산해서만들기
...acc,
[cur]: (acc[cur] || 0) + 1,
}));
const Arr = Object.entries(X); // [ ["귤크기", 갯수], ["귤크기", 갯수] ... ]
Arr.sort((a, b) => (a[1] < b[1] ? 1 : -1)); // [ ["귤크기", 갯수], ... 갯수순 정렬 ]
let total = 0;
var answer;
for (i = 0; i < Arr.length; i++) {
total = total + Number(Arr[i][1]);
if (total >= k) {
answer = i + 1;
break;
}
}
return answer;
}
solution(4, [5, 5, 5, 7, 5, 2, 2, 2, 4, 5]);
===> 58점으로 실패...
정답
function solution(k, tangerine) {
let answer = 0;
const tDict = {};
tangerine.forEach((t) => tDict[t] = (tDict[t] || 0) + 1); // [10.forEach 사용한 객체배열만들기]
const tArr = Object.values(tDict).sort((a, b) => b - a); // 정렬하기 (values 로만!)
for (const t of tArr) {
answer++; // 넣으면 answer + 1
if (k > t) k -= t; // k 가 귤수보다 클때는 k -=t
else break; // k 가 귤 수보다 작아지면 stop
}
return answer;
}
'CS와 언어, 라이브러리 이론 > 알고리즘-이론과 실전' 카테고리의 다른 글
7. [실전] - 우박수열 (1) | 2023.01.18 |
---|---|
6. [실전] - 연속 부분 수열 합의 개수 (1) | 2023.01.18 |
3. [실전] - 가장 가까운 글자찾기 (0) | 2023.01.18 |
2. [실전] - 연속되는 자연수 배열중 빈 숫자 찾기 (0) | 2023.01.18 |
1. [이론] 자주 쓰는 패턴 총 정리 - 배열편 (0) | 2023.01.18 |
댓글