알고리즘🅰/프로그래머스

[프로그래머스] 스킬트리

개발조각 2022. 5. 2. 14:35
728x90
반응형

풀긴 풀었는데 제가 푼 코드는 비효율적인 것 같아서... 해결방안 쓰기가 좀 그렇네요🤣

 

접근방법

먼저 skill에 있는 문자들의 위치를 먼저 파악했습니다.

skill = "CBD", skill_trees = ["BACDE", "CBADF", "AECB", "BDA"]

  1. "BACDE" -> [ 2, 0, 3 ]
  2. "CBADF" -> [ 0, 1, 3 ]
  3. "AECB" -> [ 2, 3, -1 ]
  4. "BDA" -> [ -1, 0, 1 ]

skill에 있는 문자들의 위치를 가지고 가능한 스킬트리를 구하기 위한 조건으로

skill에 있는 문자들의 위치들에서 -1이 있는지 없는지 부터 구분을 하였습니다.

(여기서 -1은 skill의 문자가 없을 경우)

 

-1이 없을 경우는 skill에 있는 문자가 다 있는 경우 입니다. (1번, 2번)

이럴 경우에는  skill에 있는 문자들의 위치가 오름차순인지를 확인하면 됩니다.

맞으면 스킬트리인거고 아니면 스킬트리가 아닙니다.

 

-1이 있을 경우에 -1의 위치가 어디인지 찾고 그 위치가 어디냐에 따라 -1의 개수를 구했습니다.

3번 [ 2, 3, -1 ]

  • -1의 위치 : 2
  • 3번의 길이 - 1의 개수 = 3-2 = 1

-> 3번은 -1를 1개가 있어야 됩니다.

 

4번 [ -1, 0, 1 ]

  • -1의 위치 : 0
  • 3번의 길이 - 1의 개수 = 3-0 = 3

-> 4번은 -1를 3개가 있어야 됩니다.

-> 4번의 경우는 [-1, -1, -1] 이야지 가능

 

-1의 개수가 알 맞게 있을 경우

skill에 있는 문자들의 위치에서 0부터 -1의 첫 위치 전까지만 남기고

그 배열이 오름차순인지 파악하면 됩니다. 

해결방안

function solution(skill, skill_trees) {
    let answer = 0;
    for(let i=0; i<skill_trees.length; i++){
        let skillIdx = [];
        
        for(let j=0; j<skill.length; j++){
            let idx = skill_trees[i].indexOf(skill[j]);
            skillIdx.push(idx);
        }
        
        let noIdx = skillIdx.indexOf(-1);
        if(noIdx === -1){
            let copy = [...skillIdx];
            copy = copy.sort((a,b)=>a-b);
            
            if(skillIdx.join('') === copy.join('')) answer++;
        }else{
            let count = skillIdx.length - noIdx;
            let count1 = skillIdx.filter(a=> a===-1).length;
            if(count === count1){
                skillIdx = skillIdx.slice(0,noIdx);
                let copy = [...skillIdx];
                copy = copy.sort((a,b)=>a-b);
                
                if(skillIdx.join('') === copy.join('')) answer++;
            }
        }
    }
    return answer;
}

해결방안 순서

  1. 중첩 for문을 사용하여 skill에 있는 문자들의 위치를 skillIdx에 담아주기
  2. skillIdx에서 -1이 어느 위치지 엤는지 noIdx에 담고 if else문 작성하기
  3. skillIdx에서 -1이 없으면 skillIdx랑 오름차순한 skillIdx를 비교하여 같으면 answer++해주기
  4. skillIdx에서 -1이 있으면 skillIdx에 -1이 있어야 되는 개수를 구하기
  5. skillIdx에서 -1이 있어야 되는 개수 만큼 -1이 있으면 skillIdx랑 오름차순 한 skillIdx를 비교하여 같으면 answer++해주기

 

1단계. 중첩 for문을 사용하여 skill에 있는 문자들의 위치를 skillIdx에 담아주기

function solution(skill, skill_trees) {
    let answer = 0;
    for(let i=0; i<skill_trees.length; i++){
        let skillIdx = [];
        
        for(let j=0; j<skill.length; j++){
            let idx = skill_trees[i].indexOf(skill[j]);
            skillIdx.push(idx);
        }
    }
}

indexOf()메서드를 이용해서 skill의 문자가 skill_trees문자열에서 어디에 위치하는지 찾고

push로 넣어 주었습니다.

i=0
skillIdx= [ 2, 0, 3 ]

i=1
skillIdx = [ 0, 1, 3 ]

i=2
skillIdx = [ 2, 3, -1 ]

i=3
skillIdx = [ -1, 0, 1 ]

 

 

2단계. skillIdx에서 -1이 어느 위치지 엤는지 noIdx에 담고 if else문 작성하기

let noIdx = skillIdx.indexOf(-1);
if(noIdx === -1){
	// skillIdx에서 -1이 없으면
}else{
	// skillIdx에서 -1이 있으면
}
  • noIdx : skillIdx에서 -1이 어디에 위치해 있는지(-1이 없으면 -1를 반환)
i=0
skillIdx= [ 2, 0, 3 ]
noIdx= -1
-> if문

i=1
skillIdx = [ 0, 1, 3 ]
noIdx= -1
-> if문

i=2
skillIdx = [ 2, 3, -1 ]
noIdx= 2
-> else문

i=3
skillIdx = [ -1, 0, 1 ]
noIdx= 0
-> else문

 

3단계. skillIdx에서 -1이 없으면 skillIdx랑 오름차순한 skillIdx를 비교하여 같으면 answer++해주기

if(noIdx === -1){
    let copy = [...skillIdx];
    copy = copy.sort((a,b)=>a-b);

    if(skillIdx.join('') === copy.join('')) answer++;
}
  • copy : skillIdx를 복사하여 오름차순 해줌

[0, 1 3] === [0, 1, 3]이 되면 참 좋은데 안되더라고요.

그래서 join()메서드를 사용해서 013 === 013으로 비교했습니다.

i=0
skillIdx= [ 2, 0, 3 ]
noIdx= -1
copy = [ 0, 2, 3 ]
skillIdx.join('') === copy.join('') -> 203 === 023 -> false

i=1
skillIdx = [ 0, 1, 3 ]
noIdx= -1
copy = [ 0, 1, 3 ]
skillIdx.join('') === copy.join('') -> 013 === 013 -> true임으로 answer++

 

 

4단계. skillIdx에서 -1이 있으면 skillIdx에 -1이 있어야 되는 개수를 구하기

else{
    let count = skillIdx.length - noIdx;
    let count1 = skillIdx.filter(a=> a===-1).length;
}
  • count : skillIdx에서 -1이 있어야 되는 개수
  • count1 : skillIdx에서 -1의 개수

 

i=2
skillIdx = [ 2, 3, -1 ]
noIdx= 2
let count = skillIdx.length - noIdx; -> 3-2=1
let count1 = skillIdx.filter(a=> a===-1).length; -> [-1].length -> 1
count === count1 -> true;

i=3
skillIdx = [ -1, 0, 1 ]
noIdx= 0
let count = skillIdx.length - noIdx; -> 3-0=3
let count1 = skillIdx.filter(a=> a===-1).length; -> [-1].length -> 1
count === count1 -> false;

 

 

5단계. skillIdx에서 -1이 있어야 되는 개수만큼 -1이 있으면 skillIdx랑 오름차순 한skillIdx를 비교하여 같으면 answer++해주기

if(count === count1){
    skillIdx = skillIdx.slice(0,noIdx);
    let copy = [...skillIdx];
    copy = copy.sort((a,b)=>a-b);

    if(skillIdx.join('') === copy.join('')) answer++;
}

skillIdx에서 0부터 -1이 처음으로 위치한 곳만 slice()메서드로 추출했습니다.

그래서 slice(0, noIdx)로 적어 주었습니다.

 

copy부터는 3단계와 똑같은 방법을 반복해 줍니다.

i=2
skillIdx = [ 2, 3, -1 ]
noIdx= 2
let count = skillIdx.length - noIdx; -> 3-2=1
let count1 = skillIdx.filter(a=> a===-1).length; -> [-1].length -> 1
count === count1 -> true;

skillIdx = [ 2, 3 ]
copy = [ 2, 3 ]
skillIdx.join('') === copy.join('') -> 23 === 23 -> true임으로 answer++

여기까지 프로그래머스 스킬트리 해결방안에 대해 설명해보았습니다.

728x90
반응형