귤 고르기

공부하며 느낀 점

귤 고르기

배열안에 배열을 넣어서 해결해보자

나의 풀이

생각해보니 배열안에 배열을 넣을 필요도 없다.

function sol0(k, tangerine) {
    let gyullBox = []
    const length = tangerine.length

    tangerine = tangerine.sort((q,w) => q - w)

    let gyull = 1

    for ( let i = 1 ; i <= length ; i++) {
        if ( tangerine[i] === tangerine[i-1]) {
            gyull++
        } else {
            gyullBox.push(gyull)
            gyull = 1
        }
    }

    gyullBox = gyullBox.sort((q,w) => w-q)

    let sumGyull = 0
    let i = 0
    for ( i = 0  ; sumGyull < k ; i++){
        sumGyull += gyullBox[i]
    }


    return i;
}

tangerine = tangerine.sort((q,w) => q - w) : 귤박스의 내용물을 크기순으로 정렬하고

첫 번째 for문 : 크기별로 갯수를 센다. (어떤 크기가 몇개인지는 알 필요가 없음)

gyullBox = gyullBox.sort((q,w) => w-q) : 많은 갯수 별로 내림차순 정렬한다.

두 번째 for문 : k 이상이 될때까지 더하고 더한 횟수 = 담는 귤의 종류이다.

다른 사람의 풀이

function sol1(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;
}

정렬이 필요가 없었다...
tangerine.forEach((t) => tDict[t] = (tDict[t] || 0) + 1); : 이번 요소의 이전 등장값에 1증가, (첫 등장시 이미 0을 가진것으로 설정)

for문 : 나는 더했는데 이사람은 뺐다.

속도 비교

시간 복잡도

귤의 갯수를 n, 귤의 종류를 m이라고 하면
sol0 : $O(n\log{n}+n + m\log{m}+m)$
sol1 : $O(n + m\log{m}+m)$

sort가 하나 빠진만큼 더 시간복잡도가 내려갔다.

반복 횟수 증가

왜 내거가 더 빠름?...
sort가 시간복잡도를 많이 먹지만 데이터를 정리하는 것이 그만큼의 가치를 지니는 것같다.

기왕 이래된거 입력값을 스케일 크게 늘려봤다.

데이터를 정렬하는건 매우 중요하다...

입력 길이 증가

증가율은 sol1이 더 낮지만 기본값이 10배 씩 차이나서 2배 정도 덜 증가해봐야 의미가 없다. 그래도 5배 더 걸리니까...

입력 크기 증가

입력 크기는 큰 영향을 주지 못하는 모습이다.

공부하며 느낀 점

1. sort는 분명 자원을 많이 먹는 작업이지만 그만한 가치가 있는 메서드다.
   특히 처리해야할 양이 많을 수록 더욱더 그렇다.
2. 배열안에 배열을 넣는 복잡한 구현은 피할 수 있다면 피하는 것이 좋다.