프로그래머스 - 스킬트리 (Summer/Winter Coding(~2018)) [Python]

 

 문제

 

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

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

 

 

 

 

 

 

 문제 상황

 

- 입력받은 문자열은 중복되지 않는 대문자 알파벳이며, 이 알파벳은 반드시 순서를 지켜야한다. skill_trees에서 가능한 스킬트리의 개수를 출력한다.

 

 

 

 

 

 

 해결 전략

- 기본적으로 후보군을 순회하며 스킬트리에 있는 스킬인지 확인한다. 스킬트리에 없는 것이라면 넘어가고, 스킬트리에 있는 것이면 첫번째 요소와 비교하여 첫번째 요소와 다르면 후보에서 탈락된다. 만약 첫번째 요소와 같으면 그 요소를 삭제하고 다음으로 넘어간다. 모두 통과하면 정답 수를 하나 늘린다. 

 

 

 

 

 

 

 코드

 

from collections import deque
 
 
def solution(skill: str, skill_trees: list) -> int:
    possible_skill = 0
    for test_case in skill_trees:
        # test_case를 순회하며 skill에 있지만 첫번째 요소와 다르면 false, 같으면 뺀다.
        skill_deque = deque(list(skill))
        for one_skill in test_case:
            if one_skill in skill_deque:
                if skill_deque[0] != one_skill: break
                skill_deque.popleft()
        else:
            possible_skill += 1
    return possible_skill

 

 

 

 

 

 

 

 

 해설

 

- 조건을 세분화할 필요가 있다. 직접 요소를 편집할 필요가 있는 것은 skill 뿐이고, skill 자체는 변하면 안되므로 deque로 변환한다. pop(0)은 shifting으로 속도가 느리므로 popleft를 쓰기 위해 deque를 활용했다. 

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- if-else 뿐만 아니라 파이썬에서는 for-else가 가능하다. for문과 같은 레벨에서 else가 있다면 break가 없을 때에만 else가 작동한다. Java의 경우 isCheck 등의 변수로 for문을 체크했지만 파이썬에서는 for-else로 가능하다.