순서 찾기 알고리즘 문제

1. 문제

 

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

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

 

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

 

예를 들어 선행 스킬 순서가 스파크> 라이트닝볼트> 썬더 일때,

 

썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야합니다.

 

위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다.

 

따라서 스파크>힐링> 라이트닝볼트> 썬더와 같은 스킬트리는 가능하지만 썬더>스파크나 라이트닝볼트>스파크>힐링>썬더와 같은 스킬트리는 불가능합니다.

 

선행 스킬 순서 skill과 유저들이 만든 스킬트리를 담은 배열 skill_trees가 매개변수로 주어질 때,

 

가능한 스킬 트리 개수를 return하는 함수를 완성하세요

 

 

2. 제한사항

 

스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.

 

스킬 순서와 스킬트리는 문자열로 표기합니다. 예를 들어 c>b>d라면 “CBD”로 표기합니다.

 

선행 스킬 순서 skill의 길이는 1 이상 26이하이며, 스킬은 중복해 주어지지 않습니다.

 

skill_trees는 길이 1 이상 20 이하인 배열입니다.

 

skill_trees의 원소는 스킬을 나타내는 문자열입니다.

 

skill_trees의 원소는 길이가 2 이상 26이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

 

 

3. 예시

 

 

 

 

 

4. 나의 풀이

 

skill로부터 skill의 순서를 담은 사전을 만든다

 

skill에서 스킬을 하나씩 빼서 스킬을 key로 하고 왼쪽부터 스킬의 순서를 value로 하는 사전 구성

 

def solution(skill, skill_trees):
    
    answer = 
    
    answer_list = []
    
    skill_dic = {}
    
    i = 1
    
    for order in skill:
        
        skill_dic[order] = i
        
        i = i + 1

 

다음으로 skill_trees에서 검사할 스킬트리를 하나씩 빼고

 

정해진 스킬 순서는 사전의 value에 저장되어 있으니까 value를 리스트로 만든다

 

다음 검사할 skill_tree에서 문자 하나씩 빼보는데

 

for skill_tree in skill_tress:

    order_list = list(skill_dic.values())
    
    for index,order in enumerate(skill_tree):
        
        try:
        
            a = skill_dic[order]
            
            b = order_list.pop(0)
            
            if a == b:
                
                continue
                
            else:
            
                break
        
        except:
            
            continue

 

skill_dic[order]를 통해서 해당 문자가 스킬 순서에 맞게 찍어야하는 스킬인지 확인을 해본다

 

skill_dic에 key로 존재하지않으면 에러가 발생할건데 순서에 상관없이 찍어도 되는거니까…

 

except를 통해서 continue를 시킴

 

key로 존재하면 이제 order_list의 첫번째 원소부터 뽑기 시작해(1,2,3,...이 들어가 있음)

 

b에는 1,2,3,4,...가 순서대로 들어갈거임

 

이제 첫번째로 순서에 맞게 찍어야하는 문자라면 a에 1이 들어가고 b에 1이 들어가서

 

a와 b가 같으면 순서가 맞는거니까 continue 시키고

 

a와 b가 다르면 순서에 맞게 찍지 않았다는 거니까 바로 break시킴

 

스킬 순서에 맞게 찍은 스킬트리라면 a에 1,2,3,...이 들어갈거임

 

for문을 무사히 돌았다면 index에 len(skill_tree)-1만큼 되었다는거니까

 

    if index == len(skill_tree) - 1:

        answer += 1
 
 return answer

 

 

근데 이렇게하면 몇개는 통과를 못하더라고..

 

예를 들어서 skill에 CBD가 주어질때

 

skill tree중에 AGEKB 이렇게 주어지면

 

A,G,E,K에서 for문 무사히 도는데 B에서 스킬순서에 안맞는거라서 (=C를 찍고 B를 찍어야함)

 

이건 answer에 포함을 안시켜야하는데

 

마지막 순간에 break로 탈출한거라 사실 for문을 끝까지 잘 돈거거든

 

그러면 index는 마지막까지 돈거라서 answer에 포함이 되어버림

 

다음과 같이 ind를 이용해서.

 

for skill_tree in skill_trees:
    
    order_list = list(skill_dic.values())
    
    ind = True
    
    for order in skill_tree:
    
      
        try:
            
            a = skill_dic[order]
            
            b = order_list.pop(0)
            
            if a == b:
                
                continue
                
            else:
            
                ind = False
                
                break
                
        except:
            
            continue
            
    if ind:
    
        answer += 1

 

초기에 ind=True를 한다음에

 

break문에 들어가는 경우에는 확실하게 잘못찍은거니까 ind=False로 만들고

 

for문 끝나면 ind가 True로 변하지 않았으면 제대로 찍은거니까

 

이러면 전부 통과함

 

 

5. 다른 풀이

 

사전을 안써도 깔끔하게 풀수가 있네

 

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

 

skill_trees에서 검사할 스킬트리를 skills로 하나씩 뺀다

 

스킬순서 skill을 리스트로 만드는데

 

검사할 스킬트리 skills에서 문자 하나씩 s로 빼는거지

 

만약 s가 skill에 존재한다면… s는 스킬 순서에 맞게 찍어야하는 문자임

 

존재하지 않는다면 스킬 순서에 상관없이 찍어도 되는거니까 버려도 됨

 

아무튼 순서에 맞게 찍어야되는거라면

 

이제 skill_list에서 첫번째 원소부터 pop(0)를 이용해서 뺴나가는거임

 

만약 서로 다르다면 바로 break해서 탈출하면 되는거고

 

계속 같다면 순서가 맞는거니까 다시 for문 돌면 되는거고..

 

for문을 무사히 끝까지 돌았다면 스킬 순서에 맞게 찍은거라서

 

for~ else~문을 이용해 마지막에 else문이 수행되어 answer +=1을 해줌

 

break하면 else문을 수행하지 않는다는거 어렴풋이 기억남

 

사실 if s in skill: 부분은 내가 한 try: skill_dic[order]이랑 동일한거고

 

if s != skill_list.pop(0): 부분은 내가 했던 b = order_list.pop(0)해서 a와 b를 비교했던 그거랑 동일함

 

근데 이제 나는 쓸데없이 사전을 구성했다는거에서 조금 아쉬웠다는거지

 

 

6. 되돌아보기

 

공부하니까 그런건지 계속 문제 핵심은 잘 파악하는것 같다

 

어떻게 코딩하느냐가 문제였는데

 

제한이 별로 없어서 시간 효율은 신경 안써도 된거라 상관없지만

 

사전을 구성하는건 분명 쓸데없는 부분이 맞긴하다

 

처음에 사전에 꽂혀가지고… 참…

 

in 연산이나 pop(0)같은거 많이 써서 쉽게 생각할 수 있는건데..

 

특히 in연산 생각 못한건 좀 아쉽네

 

그래도 try~except~는 사전에 key error 검사할때 많이 쓰던거니까 나쁜건 아니야

 

그래도 핵심을 잘 파악했다는거에 나쁘지 않다는거

 

 

그 외에 for~ else~문? 딱히 몰라도 되긴하는데 있다는 것정도 기억하고