[레벨2] 모음사전

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

프로그래머스

주어진 단어가 사전에서 몇 번째인지 순서를 찾는 문제이다.

dfs를 이용하여 사전 전체를 완성한 후 word의 index를 찾는 방식으로 풀어보았다.

# dfs로 사전 전부 완성 후 단어를 사전에서 찾기

def solution(word):
    vowels = ["A","E","I","O","U"]
    answer = []
    
    def dfs(cnt, lst):
        answer.append("".join(lst[:]))
        if cnt == 5:
            return
        else:
            for v in vowels:
                lst.append(v)
                dfs(cnt+1, lst)
                lst.pop()
    dfs(0,[])
    return answer.index(word)

아래와 같이 한 번에 성공하였다!

이번 문제에서는 모음만 가정하여 단어의 최대 길이가 5자이다.

하지만 최대 길이가 더 길어질 경우, 사전을 다 완성한 후 index를 찾는 방법은 효율성이 떨어질 것이다.

그래서 사전을 완성해나가다가 word가 나오면 더 이상 사전을 완성하지 않고 멈추는 방식으로 코드를 수정해보았는데..

# dfs로 사전 전부 완성 전에 멈추기

def solution(word):
    vowels = ["A","E","I","O","U"]
    answer = []

    def dfs(cnt, lst):
        if word in answer:
            return
        else:
            answer.append("".join(lst[:]))
            if cnt == 5:
                return
            else:
                for v in vowels:
                    lst.append(v)
                    dfs(cnt+1, lst)
                    lst.pop()
    dfs(0,[])
    return len(answer)-1

이상하게 효율성이 더 안좋아졌다!!

특시 테스트4의 경우는 소요 시간이 100배가 되었다.

list 자료형의 in 연산은 O(n)이어서 오래 걸릴까 싶어, answer를 in 연산이 O(1)인 set 자료형 변경 후 다시 계산해보았다.

# dfs로 사전 전부 완성 전에 멈추기
# answer를 list 대신에 set으로 수정

def solution(word):
    vowels = ["A","E","I","O","U"]
    answer = set()

    def dfs(cnt, lst):
        if word in answer:
            return
        else:
            answer.add("".join(lst[:]))
            if cnt == 5:
                return
            else:
                for v in vowels:
                    lst.append(v)
                    dfs(cnt+1, lst)
                    lst.pop()
    dfs(0,[])
    return len(answer)-1

확실히 계산 속도가 개선되었다.

몇몇 케이스 (ex. 테스트 4 등)은 첫번째보다 느려졌으나, 최대 단어의 길이가 길어질수록 세번째 코드가 더 효율적일 것이라 기대된다.