스킬 트리

16616516·2020년 9월 30일
0

알고리즘

목록 보기
8/16

def solution(skill, skill_trees):
    answer = 0
    d = [False] * 26
    
    for sk in skill_trees:
        for i in range(1, len(skill)):
            index = ord(skill[i]) - ord('A')
            d[index] = True

        skill_index = 0
        flag = False

        for i in range(len(sk)):
            if d[ord(sk[i]) - ord('A')]:
                
                flag = True
                break
            if skill[skill_index] == sk[i]:
                skill_index+=1
                if skill_index >= len(skill): 
                    skill_index-=1
                    continue
                d[ord(skill[skill_index]) - ord('A')] = False
        if not flag:
            answer+=1
    return answer

문제 해설

1) 스킬 배열을 순회하는 for문을 만든다.
2) d라는 배열을 만들고 선행스킬로 되어있는 스킬들만 True로 설정해 놓는다.
3) 선행 스킬의 순서를 저장할 skill_index변수를 만든다.
4) 최종적으로 한번이라도 어긋났는지 확인하는 변수 flag를 만든다.
5) 스킬 배열의 스킬 하나하나씩 꺼내면서 for문을 돈다.
6) 만약 지금 사용할(배울)스킬이 아직 True라면 flag를 True로 바꾸고 반복문을 종료한다.
7) 만약 지금 사용할 스킬이 선행스킬중 첫 번째 라면
8) 선행스킬 index를 증가시키고, 증가시킨 인덱스 값에 해당하는 d배열의 값을 False로 바꾸어준다.
9) 만약 최종 선행스킬까지 뚫렸다면 인덱스를 더는 증가시키지 않게 한다.

10) 마지막으로 for문을 나갈때 flag의 값으로 answer를 증가시킬지 말지 결정한다.

다른 사람의 풀이


def solution(skill, skill_trees):
    answer = 0

    for skills in skill_trees:
        skill_list = list(skill)

        for s in skills:
            if s in skill:
                if s != skill_list.pop(0):
                    break
        else:
            answer += 1

    return answer

느낀 점

스킬의 선행 목록을 list에 넣고 첫 번째와 같다면 방출해버리고 그럼으로 다음 방출될 항목은 자동으로 다음 스킬이 된다.

매우 깔끔하다.
어차피 초기화하는 시간이 길지 않음으로 이런 방식으로 하면 되겠다.
좋은 코드다.

profile
열심히 사는 사람

0개의 댓글