문제 설명
경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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
풀이 작성
내 첫 풀이가 에러가 나길래 뭘까.. 싶었는데 console.log를 너무 많이 작성하면 에러가 나더라.. '출력 크기 초과'라는 이름으로 나기 때문에 다음부터 이런 실패 사유가 뜨면 console.log를 다 지워보고 해야겠다.
여기서 중복된 귤을 어떻게 정렬하느냐가 관건인 것 같았다.
중복된 귤이 많은 숫자가 먼저 오게 나열하기.
찾아보니까 중복된 수를 나열하는 방법은 꽤 있었다. reduce, map 등.. 그 중에 나는 reduce로 풀어보았다.
return 값은 서로 다른 종류의 수의 최솟값이다. 즉, 무게가 다른 종류가 하나가 더 들어올 때 return 값이 증가된다.
function solution(k, tangerine) {
var answer = 0;
//원하는 개수를 담아둔다. 이건 아래의 for문에서 숫자가 줄어들기 때문에 복사를 해놓는 것이다. k의 숫자가 줄어들면 그만큼 for문도 안돌게 되서 계속 틀리게 된다.
var n = k
//count 값에 reduce 메소드를 써서 누적을 시켜준다. a[b] 배열에 누적값 a와 현재 요소 b를 받아서 처리한다. 이때 a[b]가 undefined인 경우를 대비하여 (a[b] || 0)으로 처리하는데 이러면 undefined일 때 0이 대신 집어넣어진다. 이를 통해 count 객체에는 각 무게별로 귤의 개수가 저장된다.
const count = tangerine.reduce((a, b) => {
a[b]=(a[b] || 0) + 1
return a;
}, {})
console.log(count)
//count는 요소로만 되어있는 게 아니고 { '1': 2, '2':1 ...} 이런식으로 저장되어 있기때문에 해당하는 값만 꺼내오는 작업이 필요하다.
//sorted는 해당 오브젝트에서 count values만 꺼내와서 크기 순서대로 정렬해준다.
const sorted = Object.values(count).sort((a, b) => b - a)
console.log(sorted)
//원하는 k 개수만큼 돌면서 개수를 세어준다.
for(let i =0 ; i < k; i++){
//먼저 종류가 들어오기 때문에 answer를 늘려준다.
answer++;
//만약 원하는 개수가 sorted[i]에 해당하는 개수보다 많으면
if(n > sorted[i])
//n에서 sorted[i] 개수만큼 빼주고 다시 돌게 된다.
n -= sorted[i]
//만약 남은 n의 개수가 sorted[i] 개수보다 작게 되면 그만 돌게 된다. 왜나면, 굳이 빼주는 작업을 하지 않아도 되고, 여기서 더 빼게되면 n은 음수가 되고 결국 그러면 k개 만큼 다 채워진 게 되기 때문이다.
else break;
console.log(n)
}
return answer;
}for문 종류에도 여러가지가 있는데, 이번에는 for of문을 가지고 문제를 푼 사람들이 많길래 이렇게도 풀어보았다.
for of는 sorted 배열의 길이만큼 i가 알아서 늘어나는 형식인 것 같았고 나머지는 다 같았다. 어차피 끝까지 돌거면 이것도 나쁘지 않은 방법 같았다. 다음에 반복문에 대해서도 다시 한번 다뤄봐야겠다!
function solution(k, tangerine) {
var answer = 0;
var n = k
const count = tangerine.reduce((a, b) => {
a[b]=(a[b] || 0) + 1
return a;
}, {})
const sorted = Object.values(count).sort((a, b) => b - a)
for(let i of sorted){
answer++
if(k > i) k-=i
else break;
}
return answer;
}