의상

1. 옷이 겹치지만 않으면 되니까 각각의 배열 길이 +1 끼리 곱하고 거기서 1(아무것도 안입는 경우)를 빼면 될것같다

2. [옷이름, 카테고리]의 형태이므로 인덱스가 1인 원소를 기준으로 정렬해야한다

3. 같은 이름의 의상은 존재하지 않으므로 인덱스가 0인 원소는 고려할 필요가 없다

풀이들

나의 풀이

function sol00(clothes) {
  let answer = 1;
  const categories = [];

  for (chloth of clothes) {
    const type = chloth[1];
    const isInCategory = categories.find((c) => c[0] === type);

    if (isInCategory) {
      isInCategory[1]++;
    } else {
      categories.push([type, 1]);
    }
  }

  for (category of categories) {
    answer = (category[1] + 1) * answer;
  }

  return answer - 1;
}

생각한데로 짰고 생각한 그대로 잘 나왔다

다른 사람의 풀이

function sol10(clothes) {
  return Object.values(clothes.reduce((obj, t)=> {
      obj[t[1]] = obj[t[1]] ? obj[t[1]] + 1 : 1;
      return obj;
  } , {})).reduce((a,b)=> a*(b+1), 1)-1;    
}

문제를 푸는 아이디어 자체는 같은데 반복문이 중첩되지 않아서 더 효율적이다

속도 비교

시간복잡도

sol00 : $O(n^2)$ for문 안에 find가 있다
sol10 : $O(n)$ reduce를 두번 실행한다

실행1

옷의 종류가 적당히 섞여있어서인지 시간복잡도가 $O(n)$인것처럼 작동한다

실행2

일부러 1번 인덱스가 모두 다르게 설정했다

내 코드는 시간복잡도에서 이득은 못봤지만 실행 속도 자체는 빨랐다. 하지만 시간 복잡도 때문에 처리할 양이 많아지면 느려지기 시작했다

느낀 점

1. 같은 수학적 판단으로 코드를 짜도 시간 복잡도가 아예 다를 수 있다

2. 지속적으로 느끼는 것이지만 시간복잡도이전에 기본 실행시간이 매우 중요하다