스킬트리

내 풀이법

문제해석

• skill 인자는 스킬을 찍는 순서를 나타냄
• skill_trees 인자의 각 배열값들이 스킬 찍는 순서에 맞게 찍었는지 확인
• skill_trees 배열 중 몇개가 순서에 맞게 찍었는지 확인

 

내가 생각한 풀이법

1. 스킬트리 각 배열의 값에 skill 값 이외를 우선 지운다
2. 스킬트리 각 배열 값들의 인덱스 값과 스킬의 인덱스 값들을 비교하며 조건에 부합한지 확인한다
   • 스킬은 중복되지 않고 고유하기 때문에 가능

나의 코드

const solution = (skill, skill_trees) => {
  let answer = 0;
  let trans = [];

  for (let i = 0; i < skill_trees.length; i++) {
    // 1. 스킬트리 각 배열값을 string에서 array로 바꿈
    let skillCheck = [...skill_trees[i]];

    for (let j = 0; j < skillCheck.length; j++) {
    // 2. 만약 스킬값 있으면 비교하기 편하게 정수(skill의 인덱스값)로 바꿈
      if ([...skill].includes(skillCheck[j])) {
        skillCheck[j] = skill.indexOf(skillCheck[j]);
    // 3. 없으면 삭제
      } else {
        skillCheck.splice(j, 1);
        j--;
      }
    }

    // 4. array 순서 확인하기. 만약에 순서가 맞지 않으면 break
    for (let k = 0; k < skillCheck.length; k++) {
      if (skillCheck[k] !== k) {
        answer--;
        break;
      }
    }
    answer++;
  }

  return answer;
};

 

코드특징

• 스킬트리 내에 불필요한 스킬들을 우선 제거했다.
• 스킬트리를 숫자로 나타내어 비교를 편하게 했다
• [0, 1, 2], [0, 1], [1, 2] 과 같은 형식으로 나타나기에 index와 값이 일치하지 않으면 옳지 않다는 것을 알 수가 있다

 

코드성능

• 이중 for문을 사용하여 성능은 뛰어나지 않다는 것을 알 수가 있다.

다른 사람 풀이법 1

function solution(skill, skill_trees) {
    var answer = 0;
    var regex = new RegExp(`[^${skill}]`, 'g');

    return skill_trees
        .map((x) => x.replace(regex, ''))
        .filter((x) => {
            return skill.indexOf(x) === 0;
        })
        .length
}

코드특징

• map함수, string.replace 메서드, 정규표현식을 통해 스킬트리 내 불필요한 스킬들을 제거한다
• filter함수, string.indexOf 메서드를 통해 스킬트리의 순서가 맞는지 확인한다 
  • 스킬이 "abcdefg"일 경우 스킬트리 순서에 올바른 경우들은 "ab", "abc", "abcd" 등 (스킬트리는 스킬의 크기보다 같거나 낮다)이기 때문에 string.indexOf를 활용할 수가 있다

•  조건에 부합하는 배열의 length를 리턴한다

 

코드성능

• 시간복잡도가 O(n)이기 때문에 나의 코드보다 훨씬 성능이 좋다

 

다른 사람 풀이법 2

function solution(skill, skill_trees) {
    function isCorrect(n) {
        let test = skill.split('');
        for (var i = 0; i < n.length; i++) {
            if (!skill.includes(n[i])) continue;
            if (n[i] === test.shift()) continue;
            return false;
        }
        return true;
    }    

    return skill_trees.filter(isCorrect).length;
}

코드특징

• filter()에 함수를 넣어서 좀 더 복잡하게 필터링을 할 수 있도록 함
• array.shift()를 사용하여 skill의 첫번째 인덱스에 해당하는 값과 비교하며 비교를 완료하면 첫번째 인덱스를 없애며 지속적으로 비교할 수 있도록 한다.

 

코드성능

• 풀이 중 성능이 제일 좋다
• 주어진 스킬에 해당하지 않은 값들을 지우지 않고 그냥 통과하는 방법을 사용해서 그런듯

오늘 배운점

• 정규표현식을 사용하면 좀 더 쉽게 원하는 코드를 표현할 수가 있다
• filter에 함수를 넣어 좀 더 편하고 복잡하게 원하는 값들로 필터링을 할 수가 있다.
• 값을 구하는 과정에서 불필요한 과정이 포함 할 수가 있다. 잘 생각하며 줄이고자 하자