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

 

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

프로그래머스

 

제한 사항에서 1이상 26이하이며, 중복된 스킬은 없다고 한다. 

 

접근법

정렬 전 후 비교로 접근

1. 모든 skill_tree에 대해 skill들을 돌면서 만약 해당 skill 이 존재한다면 skill 순서 정보와 함께 따로 list 배열에 저장. 

2. 순서 정보가 포함된 리스트이기 때문에 정렬 했을 때 스킬을 순서대로 사용했다면 정렬하기 전과 후가 같은 값이어야 함.

 

 

 

예를 들어서, "CBD" 순서대로 for 문을 돈다면, index 로 순서를 기억하자. 

즉, C 의 인덱스 (=0) tmp[0]에는 skill_tree에서 C 가 있는 원소의 index를 저장한다. 

마찬가지로 B의 인덱스(=1]) tmp[1] 에서는 skill_tree에서 B 가 있는 원소의 index를 저장한다. 

.

.

.

 

이렇게 하면 정렬하기 전 tmp과 tmp를 정렬한 tmp_sort을 비교하여 순서대로 배웠는지 확인할 수 있다. 

"BACDE" 를 예시로 하면, "CBD" 의 C 값이 있는 index 2가 제일 먼저 들어가고, B의 0 index, D의 3 index가 tmp에 저장된다. 정렬로 비교해보면, 제일 먼저 배워야하는 C 를 B보다 늦게 배운다. 정렬 하기 전과 정렬한 후의 값이 다르다. 

순서대로 배웠다면 정렬했을 때도 index 번호와 상관없이 순서는 정렬되어 있어야 하기 때문.

 

그러나 4번 예제처럼, "BDA" 에서 B,D 를 순서대로 배웠는데 C 를 배우지 않고 B 부터 먼저 배운 경우 예외 처리 해야한다.

 

만약 4번째 예제처럼, 배워야 하는 스킬을 먼저 배우지 않고 넘어갔거나 3번 예제처럼, "C B" 만 배우고 D 는 굳이 안 배웠을 경우에도 순서는 지킨 것이므로, 이때는 간단하게 26보다 큰 숫자인 27을 대신 tmp 에 append 하여 정렬을 비교할 수 있다. 

C 를 배워야하는데 C 를 배우지 않고 넘어갈 경우에, 27 이라는 숫자를 앞에 append 하기 때문에 정렬 값이 달라지는 것을 이용하는 것이다. 

 

내 코드

def solution(skills, skill_trees):
    answer = 0
        
    for sk_tree in skill_trees:
        tmp = [[] for _ in range(len(skills))]
        for i, skill in enumerate(skills):
            if skill in sk_tree:
                tmp[i].append(sk_tree.index(skill))
            else:
                tmp[i].append(27)
        
        tmp_sort = sorted(tmp)
        if tmp_sort == tmp:
            answer +=1
    return answer

 

 

다른 사람 풀이

def solution(skill,skill_tree):
    answer=0
    for i in skill_tree:
        skillist=''
        for z in i:
            if z in skill:
                skillist+=z
        if skillist==skill[0:len(skillist)]:
            answer+=1
    return answer

 

배워야하는 스킬의 문자열들만 따로 저장해서 원본과 문자열 순서 그대로 비교한다는 점에서 간단한데 아이디어가 괜찮다고 생각해서 갖고 옴.