프로그래머스 스킬트리(Lv2)

문제

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

내풀이

def solution(skill, skill_trees):
    answer = 0
    
    d = {"A":99,"B":99,"C":99,"D":99,"E":99,"F":99,"G":99,"H":99,"I":99,"J":99,"K":99,"L":99,"M":99,"N":99,"O":99,"P":99,"Q":99, "R":99, "S":99, "T":99,"U":99,"V":99,"W":99,"X":99,"Y":99,"Z":99}
    
    order = 1
    
    for i in skill:
        d[i] = order
        order += 1
    
    for i in skill_trees:
        arr = list(i)
        check = True
        current = 1
        
        for j in range(len(arr)):
            if d[arr[j]] == current:
                current += 1

            else:
                if d[arr[j]] != 99:
                    check = False
                    break
                
                
        if check == True:
            answer += 1
            
    
    return answer 

결과

다른풀이

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 로 skill_trees를 돌리며 비교했는데
다른분은 skill_trees를 가지고 skill 을 돌리며 비교했다

길이가 20이하인 배열이라고 주어져서 시간복잡도가 충분하기에 문제에서 준대로 아주 정직하게 그대로 구현했는데 다른풀이처럼 skill_trees를 앞에부터 보면서 skill의 첫값과 비교하면 스킬순서 dict를 따로 안만들어줘도 될것같다!

다른분 코드가 훨씬 짧지만 그래도 dict도 시간복잡도는 O(1)로 빠르기에 나름 내코드도 빠르지 않을까 하는 생각에 한번 둘다 돌리면서 시간비교를 해봤다!!

소스를 축소해놨지만 solution1이 내풀이, solution2가 다른풀이 이다.
워낙에 금방끝나는 작업이라 10만번씩 돌렸는데
평균 2배~3배정도 시간차이가 나는듯하다!..

시간차이 가장 적게나는걸로 올리려고 한번 계속돌려봤는데 부질없다.. 메이플 주사위 44 감성
아 .. 아까 2배밖에 차이 안났을때 그냥 캡처할껄..

새로 공부한것

문자열 ---> 배열 변환하기

a = "hello"
list_a = list(a)
list_a    // ['h','e','l','l','o']

띄어쓰기나 특정 구분자로 변환하는건 많이해봤는데 >> a.split()
통으로 변환하는건 안써봐서 찾아봤다

그냥 list로 통으로 한번 묶어주면 된다!

공부끝!