🎯 문제

문제 출처

Lv.2 귤 고르기 - JavaScript

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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

❓ 풀이 과정

먼저, 문제의 접근 방식은 매우 간단하다.

접근 방식

1. '귤의 종류 : 귤의 갯수'를 'key : value'로 가지는 해시테이블을 만든다.
2. 해시테이블의 값을 모아 내림차순으로 정렬한다.
3. 큰 것부터 차례대로 그리디하게 선택한다.

첫번째 풀이 (시간초과)

이러한 접근 방식으로 작성한 나의 첫번째 풀이는 아래와 같다.

function solution(k, tangerine) {
  // 해시테이블 만들기
  const table = {};
  for (let t of tangerine) {
    if (Object.keys(table).includes(`${t}`)) {
      table[t]++;
    } else {
      table[t] = 1;
    }
  }

  // 해시테이블의 value를 내림차순 정렬
  const kind = Object.values(table).sort((a, b) => b - a);

  // 귤의 종류 count
  let count = 0;
  
  // kind의 값을 차례대로 k에서 빼나간다.
  // k의 값이 0보다 같거나 작아지면 이 과정을 종료한다.
  for (let num of kind) {
    if (k <= 0) break;
    count++;
    k -= num;
  }
  return count;
}

하지만, 시간초과 발생!

어디서 시간초과가 났을까?

문제 자체는 매우 간단했기 때문에, 접근방식에 문제가 있을리는 없었다. 코드 중 어느 부분이 시간 초과를 발생하고 있는 것이 분명했다.

시간초과가 어디서 났는지 알아보기 위해 코드의 한 부분씩 정답코드로 고쳐 답안을 제출해보고 채점된 시간을 비교해봤다. 결론적으로 시간초과가 발생한 부분은 코드 상단에 해시테이블을 만드는 부분이었다.

코드 비교

1. 나의 코드
   • 채점시간 : 1988.26ms

  const table = {};
  for (let t of tangerine) {
    if (Object.keys(table).includes(`${t}`)) {
      table[t]++;
    } else {
      table[t] = 1;
    }
  }

2. 정답 코드
   • 채점시간 : 3.62ms

const table = {};
tangerine.forEach((n) => {
    table[n] = ++table[n] || 1;
  });

채점된 시간을 보면 최악의 경우 600배 이상 차이가 나는 것을 볼 수 있다.

시간초과 발생하는 이유 (시간복잡도 설명)

결론적으로 시간초과가 발생하는 이유는 includes 메소드 때문이다. 각각 for문과 forEach를 사용하여 배열을 순회하고 있기 때문에 두 풀이 모두 시간복잡도는 동일하게 'O(n)'이다.

하지만 나의 풀이는 includes 메소드를 사용하여 상수 시간이 많이 걸린다. includes 메소드는 최악의 경우 'O(n)'의 시간 복잡도를 가질 수 있기 때문이다.

이 경우 입력 크기가 작을 때는 차이가 크게 나타나지 않을 수 있지만 입력 크기가 커질수록 속도 차이가 많이 난다. 입력 크기에 대해 상수 시간이 선형적으로 증가하기 때문이다.

결론!

해시테이블을 만들 때 해당 키가 있는지 확일할 때는
tangerine.forEach((n) => {table[n] = ++table[n] || 1;});와 같은 코드를 쓰자.

💡 전체 코드

function solution(k, tangerine) {
  // 해시테이블 만들기
  const table = {};
  tangerine.forEach((x) => (table[x] = ++table[x] || 1));

  // 해시테이블의 value를 내림차순 정렬
  const kind = Object.values(table).sort((a, b) => b - a);

  // 귤의 종류 count
  let count = 0;
  // sorted_table_keys를 차례대로 table에서의 값을 조회하여 k를 빼나간다.
  for (let num of kind) {
    if (k <= 0) break;
    count++;
    k -= num;
  }
  return count;
}