[프로그래머스] 스킬트리(LV.2) by javascript - Summer/Winter Coding(~2018)

▷ 문제 : Summer/Winter Coding(~2018) - 스킬트리 LV.2

코딩테스트 연습 - 스킬트리

▷ 해결 날짜 : 2022.05.13
▷ 소요 시간 : 30분
▷ 풀이 과정 :

 

아래와 같은 입력이 주어진다고 한다.

skill	skill_trees	return
"CBD"	["BACDE", "CBADF", "AECB", "BDA"]	2

skill_trees중에서 배울 수 있는 skill_tree의 개수를 반환하면 되는 문제다.

skill의 대상이 아닌 것들은 순서가 상관없고 skill의 대상이면 skill순서대로 스킬을 배워야 한다.

여기서 중요한 제한 조건은 

• 스킬이 중복해 주어지지 않습니다.

라는 제한 조건이다.

 

결국 순서라는 게 있기 때문에 정규표현식을 쓰면 어떨까 라는 생각이 들었다.

1. 정규표현식으로 배열의 각 문자열을 skill을 제외한 나머지는 지워버린다.

2. 그리고 남은 문자열로 skill과 비교해서 순서가 맞는지 체크한다.

2-1. 여기서 그냥 skill 자체가 있는 indexOf를 해도 될 거라는 생각이 들었지만 만약 CB만 배울 경우 indexOf로는 전부 체크가 불가능하다 여겨 every로 체크를 해주도록 한다.

 

라는 순서로 구현을 해보았다.

 

▷ 구현

function solution(skill, skill_trees) {
    return skill_trees
            .map(e => e.replace(new RegExp(`[^${skill}]`,'gi'), ''))
            .filter(e => e.split('').every((v, i) => skill[i] === v)).length;
}

▷ 복기 :

오랜만에 다시 알고리즘을 풀기로 마음먹었는데, 나름 재밌는 문제였다.

아직까지도 이중 반복문이 가장 먼저 머릿속에 떠오르는데, 사실 그것도 괜찮게 느껴진다 어쨌든 풀 수 있는 문제라는 거니까 그 상태에서 시간 복잡도를 위해 고민하고 개선하면 좋은 코드가 나올거라 생각된다.

(사실 위 문제는 시간복잡도를 생각해봤지만 결국 filter 안에 every를 사용함으로 이중 반복문과 크게 다를게 없어졌다...)