프로그래머스 스킬트리

문제 설명

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

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

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

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

제한 사항

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

입출력 예

skill	skill_trees	return
"CBD"	["BACDE", "CBADF", "AECB", "BDA"]	2

입출력 예 설명

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

풀이

• 이거 너무 쉽지 않냐?

def solution(skill, skill_trees):
    answer = 0
    lst1 = list(skill)
    lst2 = list(skill_trees)
    for st in skill_trees:
        lst2 = list(st)
        lst2 = [i for i in lst2 if i in lst1]
        is_passed = False
        for i in range(len(lst2)):
            if lst2[i] == lst1[i]:
                is_passed = True
                pass
            else:
                is_passed = False
                break
        if is_passed == True:
            answer += 1
    return answer

• ㅇㅇ 쉽지않아... 뭐가 틀린거야?

정확성  테스트
테스트 1 〉	실패 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.02ms, 10.1MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	실패 (0.07ms, 10.3MB)
테스트 6 〉	실패 (0.01ms, 10.1MB)
테스트 7 〉	실패 (0.03ms, 10.3MB)
테스트 8 〉	실패 (0.02ms, 10.1MB)
테스트 9 〉	실패 (0.03ms, 10.3MB)
테스트 10 〉	실패 (0.02ms, 10.2MB)
테스트 11 〉	실패 (0.02ms, 10.1MB)
테스트 12 〉	통과 (0.06ms, 10MB)
테스트 13 〉	실패 (0.04ms, 10.2MB)
테스트 14 〉	실패 (0.02ms, 10.1MB)

• 아! 중간에 뭐 있으면 안되는거야???
• CBD가 돼니까, CB, BD는 되고, CAB는 안되는건가? 참나... ㅡ.ㅡ`

def solution(skill, skill_trees):
    answer = 0
    lst1 = list(skill)
    for s_tree in skill_trees:
        s_list = list(s_tree)
        lst2 = [(s_list[i],i) for i in range(len(s_list)) if s_list[i] in lst1]
        lst2 = dict(lst2)
        check = -1
        for i in lst2.values():
            if check == -1:
                check = i
            else:
                if check+1 == i:
                    pass
                else:
                    check = -1
                    break
        if check != -1:
            answer += 1
    return answer

• 아니야... 문제 읽어보면 맨 처음 짠 거 맞아. 근데 왜 실패 뜨지?

def solution(skill, skill_trees):
    answer = 0
    lst1 = list(skill)
    print(lst1) # 이 순서대로 되어 있는지 체크해야 함
    for skill_tree in skill_trees:
        lst2 = list(skill_tree)
        lst2 = [_ for _ in lst2 if _ in lst1]
        is_passed = False
        for i in range(len(lst2)):
            if lst2[i] == lst1[i]: #같으면?
                print(lst1, lst2, i, "번째 같음") # 비교
                is_passed = True
            else:
                print(lst1, lst2, i, "번째 다름") # 비교
                is_passed = False
                break
        if is_passed == True:
            answer += 1
    return answer

• 혹시 이렇게 하면 순서가 틀어진다거나 하나?
  • lst2 = list(skill_tree)
  • lst2 = [_ for _ in lst2 if _ in lst1]
• 그래서 append로 바꿔보았으나 똑같은 에러 발생
  • lst2 = []
  • for l in skill_tree:
  •     if l in lst1:
  •        lst2.append(l)
• 아 뭐지? 이상해 이상해 이상해.
  • 리스트가 같은 리스트가 아닌건가?
• 좀 고쳐봄. 근데 통과됨.
  • 뭐야? 왜 이래???
  • 문자열을 리스트로 만들거나 for문 돌려서 만들거나 똑같다.
  • 기존 리스트가 아닌 새로운 리스트를 만드는 게 해결 방법이었다.
  • 뭔가 꼬이나봄?

def solution(skill, skill_trees):
    answer = 0
    lst1 = list(skill)
    for skill_tree in skill_trees:
        lst2 = [_ for _ in skill_tree if _ in lst1]
        is_passed = True
        for i in range(len(lst2)):
            if lst2[i] != lst1[i]:
                is_passed = False
                break
        if is_passed == True:
            answer += 1
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.01ms, 10MB)
테스트 2 〉	통과 (0.01ms, 10.3MB)
테스트 3 〉	통과 (0.02ms, 10.2MB)
테스트 4 〉	통과 (0.02ms, 10.3MB)
테스트 5 〉	통과 (0.03ms, 10.3MB)
테스트 6 〉	통과 (0.02ms, 10.2MB)
테스트 7 〉	통과 (0.02ms, 10.1MB)
테스트 8 〉	통과 (0.02ms, 10.2MB)
테스트 9 〉	통과 (0.02ms, 10.3MB)
테스트 10 〉	통과 (0.02ms, 10.1MB)
테스트 11 〉	통과 (0.03ms, 10.2MB)
테스트 12 〉	통과 (0.03ms, 10.1MB)
테스트 13 〉	통과 (0.02ms, 10.1MB)
테스트 14 〉	통과 (0.01ms, 10.2MB)

• 고수의 풀이
  • 문자열을 리스트로 바꿀 필요 없이, 그냥 문자열로 확인해도 되나보다.

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
    
테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.4MB)
테스트 3 〉	통과 (0.01ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.3MB)
테스트 5 〉	통과 (0.02ms, 10.2MB)
테스트 6 〉	통과 (0.01ms, 10.1MB)
테스트 7 〉	통과 (0.01ms, 10.3MB)
테스트 8 〉	통과 (0.01ms, 10.3MB)
테스트 9 〉	통과 (0.01ms, 10.2MB)
테스트 10 〉	통과 (0.01ms, 10.2MB)
테스트 11 〉	통과 (0.02ms, 10.2MB)
테스트 12 〉	통과 (0.02ms, 10.2MB)
테스트 13 〉	통과 (0.01ms, 10.1MB)
테스트 14 〉	통과 (0.01ms, 10.3MB)

• 이거도 비슷

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
    
정확성  테스트
테스트 1 〉	통과 (0.00ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.1MB)
테스트 5 〉	통과 (0.01ms, 10MB)
테스트 6 〉	통과 (0.01ms, 10.2MB)
테스트 7 〉	통과 (0.01ms, 10.1MB)
테스트 8 〉	통과 (0.01ms, 10.3MB)
테스트 9 〉	통과 (0.01ms, 10.1MB)
테스트 10 〉	통과 (0.01ms, 10MB)
테스트 11 〉	통과 (0.01ms, 10.1MB)
테스트 12 〉	통과 (0.02ms, 10.2MB)
테스트 13 〉	통과 (0.01ms, 10.3MB)
테스트 14 〉	통과 (0.01ms, 10.2MB)

• 아 그리고 내 코드가 통과 안된 이유를 잘 모르겠다. 이 부분인데...
  • lst2 = list(skill_tree) #스킬트리를 리스트로 변환한 걸 참조하는 lst2란 변수를 만듬.
  • lst2 = [_ for _ in lst2 if _ in lst1] #그 변수 lst2에서 원소들 반복문으로 체크해서 lst1에 없는 건 지움.
  • lst2가 여러번 참조되면서 꼬이는 부분? 확실이 이 부분 때문에 실패가 나고 있었다.
    • 왜 그런지는 몰?루