[프로그래머스 | 2단계] 스킬트리(문자열이 순서대로 있는가)

 

https://programmers.co.kr/learn/courses/30/lessons/49993

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

 

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다.

예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다.

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다.

선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

제한 조건

• 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.
• 스킬 순서와 스킬트리는 문자열로 표기합니다.
  • 예를 들어, C → B → D 라면 "CBD"로 표기합니다
• 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다.
• skill_trees는 길이 1 이상 20 이하인 배열입니다.
• skill_trees의 원소는 스킬을 나타내는 문자열입니다.
  • skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

입출력 예

skillskill_treesreturn

"CBD"

["BACDE", "CBADF", "AECB", "BDA"]

2

입출력 예 설명

• "BACDE": B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다.
• "CBADF": 가능한 스킬트리입니다.
• "AECB": 가능한 스킬트리입니다.
• "BDA": B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

 

 

문제풀이

 

문제해결

1. 딕셔너리를 만들어서 skill에 있는 알파벳을 키, 밸류는 인덱스로 만든다

 {

     C : 0,

     B : 1,

     D : 2

}

2. skill_trees를 하나 뽑기

 - "BACDE"

3. skill_trees에 한글자를 딕셔너리의 키로 skill의 순서 인덱스를 확인한다

 - check[dic[i]]

 - B의 인덱스는 1 

4. 일단 확인한 인덱스로 check에 그 인덱스를 true로 변경

 - check[1] = true

 [[false], [true], [false]]

5. 변경한 인덱스부터 앞에 다 true로 변경되어있는지 확인, 안되어있으면 순서대로 잘못된 스킬트리

 - check[1]이 true인데 check[0]이 false이다 ====> 잘못된 스킬트리!

 

def solution(skill, skill_trees):
    count = 0
    dic = {}
    
    #스킬 종류와 유지해야하는 순서의 인덱스를 딕셔너리로 저장
    #{키=스킬종류 : 밸류=순서번호}
    for i in range(len(skill)) :
        dic[skill[i]] = i
    
    for skill_tree in skill_trees :
        check = [False] * len(skill)        #딕셔너리의 키 값으로 스킬트리 순서 유지 확인용
        flag = True                         #플래그 값을 계속 True로 유지해야 올바른 스킬 트리 유지
        
        #스킬 한개씩 쪼개서 비교
        for s in skill_tree :
            #트리에 스킬셋 관련된 스킬이 포함되어 있는 경우
            if s in skill :
                check[dic[s]] = True        #스킬이 확인되면 check에 해당 순서에 맞게 true로 바꿔줌
                
                #check가 0부터 dic[s]인덱스 앞까지 모두 True로 변환되어 있었어야함(그래야 올바른 스킬테크)
                for i in range(dic[s]) :
                    if check[i] == False :
                        flag = False
                        break
        if flag == True :
            count += 1
            
    return count

 

 

자바스크립트 코드

function solution(skill, skill_trees) {
    let count = 0;
    let dic = {}
    
    //스킬 종류와 유지해야하는 순서의 인덱스를 딕셔너리로 저장
    //{키=스킬종류 : 밸류=순서번호}
    for (let i = 0; i<skill.length; i++) {
        dic[skill[i]] = i
    }
    
    //skill_trees의 스킬트리 하나씩 뽑으면서 확인
    skill_trees.forEach((skill_tree) => {
        let check = new Array(skill.length)
        let flag = true

        //스킬 한개씩 쪼개서 비교
        skill_tree = String(skill_tree).split("")
        //트리에 스킬셋 관련된 스킬이 포함되어 있는 경우
        skill_tree.forEach((s) => {
            if (s !== -1) {
                check[dic[s]] = true    //스킬이 확인되면 check에 해당 순서에 맞게 true로 바꿔줌
                
                //check가 0부터 dic[s]인덱스 앞까지 모두 True로 변환되어 있었어야함(그래야 올바른 스킬테크)
                for(let i = 0; i < dic[s]; i++) {
                    if (check[i] === undefined ) {
                        flag = false
                        break
                    }
                }
            }
        })
        if (flag == true) {
            count += 1
        }
    })
    return count;
}