문제의 발단

몬스터 헌터 와일즈의 장비 조합 사이트를 개발중이다. 무기와 장식주 조합은 완료지만 방어구는 아직이다.

for (const head of headArmors) {
  for (const chest of chestArmors) {
    for (const arms of armArmors) {
      for (const waist of waistArmors) {
        for (const legs of legArmors) {
          for (const charm of charms) {

              result.push({
                head: head as Armor,
                chest: chest as Armor,
                arms: arms as Armor,
                waist: waist as Armor,
                legs: legs as Armor,
                charm: charm as Armor,
              });
            }
          }
        }
      }
    }

별다른 생각 없이 위와같은 코드를 짰다. 그냥 조합이 필요 했으니까...

하지만 브라우저가 멈추는 것이 아닌가? 당연한 것이다

10개씩만 있다고 가정해도 $10^6$ = 100만이고 30개라면 $30^6$ 7억 2900만 이다. 멈추는게 당연했다.

예측되는 해결법

1. 일정 갯수로 자르기
2. 특정 기준으로 필터링을 하기

품질을 따져야하기 때문에 특정 기준으로 각각 파츠들을 필터링하고 조합이 너무 많으면 자르는 방식을 취해야겠다.

기준을 어떻게 나눌 것인가?

우선 방어구를 최대한 걸러서 조합의 수를 줄임과 동시에 조금이라도 가능성이 있는 방어구는 남겨야한다는 모순된 목표를 달성해야한다.

방어구에 내가 원하는 스킬이 없다면 이것은 슬롯으로 대체가 된다. 예를 들어 스킬A의 3레벨이 필요하다면 스킬A를 가지고 있지 않더라도 3레벨 슬롯을 가진 방어구는 조합에 사용이 가능할 것이다. 또는 1레벨 슬롯이 있더라도 다른 방어구들에서 스킬A를 2레벨 챙겼따면 1레벨 스킬 장식품을 넣어서 만족이 된다. 이는 매우 유용한 전략이지만 100%정도의 방어구가 필터링을 통과해 버릴 것이다.

0. 기본 설정을 하위 방어구는 제외한다 : 이것만으로도 많은 방어구가 줄어들어서 도움이 될 것이다. G급이 나온다면 상위는 감마 방어구만 포함하는걸 기본으로?

1. 3레벨 이상의 슬롯만 남긴다면? : 그럴듯해보이는 방식이지만 실제로 몬헌 와일즈의 장식품은 1~3레벨이 모두 존재하는 경우, 2~3레벨만 존재하는경우, 1레벨만 존재하는경우, 2레벨만 존재하는 경우, 3레벨만 존재하는 경우들이 있다.

2. 3레벨 슬롯 1개이상 or 2레벨슬롯 2개이상 or 1레벨 슬롯 3개이상 : 슬롯 레벨을 1점으로 생각한다면 원하는 스킬이 없더라도 3점 이상의 방어구만 필터링 한다? 괜찮아보이지만 너무 많은 방어구들이 통과해버린다.

3. 슬롯은 방어구 조합에서 우선순위를 낮추고 원하는 방어구들이 있는 방어구를 우선으로한다? : 개발사에서 의도한 방어구 조합 또는 그것보다 조금 더 좋은 조합은 찾기 쉬울 수 있을 것같다.

예상 알고리즘

0. 방어구의 파츠와 호석마다 "없음"방어구와 특정슬롯 방어구(3,2,1 또는 2,2같은 것들)을 추가해서 조합에서 최고의 우선순위를 가지게한다. 없음이나 특정슬롯 방어구로 불가능하다면 일반 방어구 파츠를 하나씩 섞는다
   기존 방어구들의 slots도 제2의 타입처럼 사용한다

1. 선택된 스킬들을 [스킬레벨 * 장식품의 슬롯레벨] 로 점수화한다

2. 점수가 높은 스킬들을 만족하는 호석들을 먼저 선택한다

3. 방어구에 내가 원하는 스킬이 있다면 통과

4. 원하는 스킬이 없더라도 원하는 스킬 장식주의 레벨 이상의 슬롯이 있다면 통과
   예) 도전자와 귀마개는 1레벨을 위해 3, 2 레벨의 슬롯이 필요 하기 때문에 1레벨 슬롯은 계산에서 제외한다.
   다만 이것은 가장 레벨이 낮은 장식주 슬롯을 기준으로 한다.
   예) 도전자5, 귀마개2가 필요하지만 둘 다 없는 방어구, 그렇다면 가장 작은 슬롯레벨은 2이므로 2이상의 슬롯이 있는 방어구는 스킬이 없더라도 남긴다.
   예) 도전자5, 귀마개2, 납도술3이 필요하다. 셋다 없는 방어구지만 납도술이 1슬롯레벨을 요구하므로 1이상의 슬롯이 있다면 남긴다.
   예) 도전자5, 귀마개2, 납도술3이 필요하다. 납도술3이 이미 달려있어서 납도술이 필요 없으므로 가장 작은 슬롯이 2레벨 이상이 있는 방어구만 남기낟

5. 5 종류의 방어구 + 1개의 호석의 조합을 한다

6. 필요하다면 특정 속성의 방어력을 10이상 20미만, 20이상으로 선택하는 필터링 선택지를 둔다

7. 끝나면 거기에 장식품을 넣는다
   무기 장신구 조합을 참고, 변형하기, 어떤 방어구에 어떤 장신구를 넣을지는 판단하지 않는다. 어떤 방어구에 넣든 똑같기 때문이다.

8. def 배열에서 두번째 값의 합이 높은 순서대로 배열