[프로그래머스] 스킬트리 파이썬

어라.. 왜 한 번에 풀었지? 

시간 복잡도는 O(N^2)이다. 어떻게 구현하지 생각하다가 .index()를 생각했다.

아래는 개자 작성한 코드 주석을 달아놨다.

 

def solution(skill, skill_trees):
    answer = 0
    
    for tree in skill_trees:
        lev = 0 #선행스킬을 아무것도 안 배움
        bol = True #for문 다 돈 다음 무사 통과했는지 확인
        for sk in tree:
            if (sk in skill):
                if skill.index(sk) <= lev: #선행스킬과 skill의 레벨 검사
                    lev += 1
                else:
                    bol = False #무사통과 못 함
                    break
        if bol: #무사통과함
            answer += 1 
     
    return answer

 

이 코드의 가장 큰 문제는 if skill.index(sk) <= lev이다. 사실 같은 스킬을 더 올리는 경우가 없어서 이 테스트는 통과한거다. 

만약 ABC 이렇게 선행스킬인데 스킬트리에서 AAAC 이렇게 올려도 되나? 를 묻는다면

 

내 코드로는 이게 당연히 PASS가 되어버린다.

 

다른 사람 코드를 공부 해보자. 

 

def solution(skill, skill_trees):
    answer = 0

    for skills in skill_trees:
        skill_list = list(skill) # 선행스킬을 리스트화 함 pop 사용하기 위해서

        for s in skills:
            if s in skill: 
                if s != skill_list.pop(0): # 즉 선행스킬에는 있는데 그 순서를 안 지키면 break
                    break
        else:
            answer += 1

    return answer

skill, skills, skill_list 등 변수명이 비슷비슷해서 헷갈릴 수 도 있다!

 

일단 시간 복잡도는 둘 다 O(N^2)이다.

 

근데 for 문이 무사히 끝나면 else 문이 실행된단다.. for else 를 파이썬이 지원한다는 것을 처음 알았다 신기하다 ㅋㅋ

 

내 고민을 pop(0)을 통해서 말끔히 해결한 코드다.

 

pop으로 skill_list에서 아에 빼버리니까 다음에 AAA 이렇게 와도 s in skill에 걸리지 않는다!

 

게다가 순서대로 되어있으니 와.. 역시 공부해야한다!

 

코드를 읽으며 이해는 되는데 뭐라해야하지 

 

코드가 내 소유가 되지는 못 한 느낌이다.