[프로그래머스] 귤 고르기 | JavaScript

문제출처

1. 문제

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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가지로, 이 값이 최소가 됩니다.

2. 풀이

처음에는 배열을 이용해 코드를 작성했다.

• 귤의 크기를 index로 하고, 해당하는 index 값에 해당하는 크기의 개수를 넣어 배열을 만들었다.
• while문을 이용하여 배열의 max 값을 찾아 k에서 해당 값을 빼는 코드는 작성했다.

하지만 런타임 에러가 발생했다.
원인은 new Array()로 배열을 만들 때 Math.max(...tangerine)의 크기로 만들었는데 크기가 커지면서 메모리 초과가 발생한 것으로 보인다.
코드는 아래와 같다.

// 런타임 에러 발생한 코드

function solution(k, tangerine) {
  let res = 0;
  let size_idx = new Array(Math.max(...tangerine) + 1).fill(0);
  tangerine.map((e) => (size_idx[e] += 1));
  while (k > 0) {
    let max_size = Math.max(...size_idx);
    k -= max_size;
    size_idx[size_idx.indexOf(max_size)] = 0;
    res += 1;
  }
  return res;
}

따라서 배열 말고 객체를 사용하는 방식으로 코드를 수정했다.

• 귤의 크기를 key, 해당하는 크기의 개수를 value로 하는 객체를 생성했다.
• 객체에서 value를 배열로 만들어서 오름차순으로 정렬한다.
• for문을 이용하여 k에 배열의 값을 차례대로 빼줘서 k가 0 이하가 되면 break 한다.

아래와 같이 작성하였더니 런타임 에러가 발생하지 않았고, 해당 문제를 패스할 수 있었다.

function solution(k, tangerine) {
  let res = 0;        // 서로 다른 종류의 수
  let size_obj = {};  // 크기: 개수

  // size_obj에 크기 없다면 객체에 추가, 있다면 개수 += 1
  tangerine.map((e) => {
    if (!(e in size_obj)) size_obj[e] = 1;
    else size_obj[e] += 1;
  });

  // size_obj의 value만 배열로 만들어서 오름차순 정렬
  size_arr = Object.values(size_obj).sort((a, b) => b - a);

  // 한 상자에 담으려는 귤의 개수가 0 이하가 될 때까지 귤 개수 빼주기
  for (let i = 0; i < size_arr.length; i++) {
    k -= size_arr[i];
    res += 1;
    if (k <= 0) break;
  }

  return res;
}

3. 다른 사람의 풀이

아무래도 알고리즘을 풀 때 파이썬을 오래 사용하다보니 자바스크립트 코드가 파이썬스러운(?) 느낌이 많이 나는 편이다.
다른 사람들의 풀이 중 자바스크립트 느낌이 낭낭한 코드가 있어서 가져왔다.

• 내가 map을 사용한 것과 달리 forEach와 ||를 사용하여 객체에 해당하는 키 값이 있다면 기존 값에 1을 더하고, 없다면 0을 반환한다.

이외의 코드는 내 코드와 유사하지만 forEach와 ||를 능숙하게 사용한다는 점이 배울만하다.

function solution(k, tangerine) {
  let answer = 0;
  const tDict = {};
  tangerine.forEach((t) => tDict[t] = (tDict[t] || 0) + 1);
  const tArr = Object.values(tDict).sort((a, b) => b - a);
  for (const t of tArr) {
    answer++;
    if (k > t) k -= t;
    else break;
  }
  return answer;
}