[TIL] 99클럽 코테 스터디 7일차 TIL - <프로그래머스 : 10561 징검다리> 문제 풀이 with python

Today's keyword : 그래프이론

 

문제설명

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

프로그래머스

"모음 사전" 문제는 주어진 모음(A, E, I, O, U)으로 만들 수 있는 모든 가능한 단어를 나열된 사전에서 특정 단어의 순서를 찾는 문제입니다. 단어의 길이는 1부터 5까지이며, 중복된 단어는 허용되지 않습니다. 

문제풀이

문제풀이1. Product 사용 

사전을 구성하는 모음이 5개로 많지 않기 때문에 product을 이용해 모든 가능한 단어를 사전으로 만들어 나열한 후, 주어진 단어의 위치를 반환하도록 코드를 작성하였습니다.  

def solution(word):
    lst = ['A', 'E', 'I', 'O', 'U']
    from itertools import product
    dictionary = []
    for i in range(1, 6): 
        pm = product(lst, repeat=i)
        for j in pm: 
            print(j)
            dictionary.append(''.join(j))

    dictionary = sorted(dictionary)
    answer = dictionary.index(word) + 1
    return answer

1. 모음 리스트 정의: A, E, I, O, U를 리스트에 저장합니다.
2. 조합 생성: 1부터 5까지의 길이에 대해 itertools.product를 사용하여 모든 가능한 조합을 생성합니다.
3. 조합 저장: 생성된 조합을 문자열로 변환하여 dictionary 리스트에 추가합니다.
4. 정렬: sorted를 이용해 정렬하여 사전 순으로 나열합니다.
5. 인덱스 찾기: 주어진 단어의 인덱스를 찾아 반환합니다. 인덱스는 1부터 시작하므로, +1을 합니다.

문제풀이2. 그래프 이론 - DFS

해당 문제의 분류가 그래프 이론으로 되어 있기 때문에 그래프 이론을 활용하여 해당 문제를 해결하는 방법은 DFS를 사용하는 것입니다. 각 모음의 조합을 트리 구조로 생각하고 각 깊이에 모음을 추가하여 단어를 생성하여 원하는 단어의 순서를 찾습니다. 

def solution(word):
    lst = ['A', 'E', 'I', 'O', 'U']
    count = 0
    answer = 0

    def dfs(current, depth):
        nonlocal count, answer
        if depth > 5:  # 최대 깊이 5
            return
        if current:  # 현재 단어가 비어있지 않으면
            count += 1  # 단어의 순서 카운트
            if current == word:  # 현재 단어가 찾고자 하는 단어와 같으면
                answer = count  # 인덱스 저장
                return
        
        for vowel in lst:  # 각 모음에 대해
            dfs(current + vowel, depth + 1)  # 모음을 추가하여 재귀 호출

    dfs("", 0)  # DFS 시작
    return answer  # 찾은 단어의 인덱스 반환

1. DFS 함수: dfs 함수는 현재 문자열(current)과 깊이(depth)를 인자로 받습니다. 깊이가 5를 초과하면 종료합니다.
2. 단어 카운트: 현재 문자열이 비어있지 않으면 카운트를 증가시킵니다.
3. 단어 비교: 현재 문자열이 찾고자 하는 단어(word)와 같으면 인덱스를 저장하고 종료합니다.
4. 재귀 호출: 각 모음(A, E, I, O, U)을 추가하여 재귀적으로 호출합니다.

두 방법 비교

product을 사용하게 되면 코드가 직관적이기 때문에 이해하기 쉽지만, 모든 조합을 생성한 다음 정렬을 진행하기 때문에 메모리와 시간 측면에서 비효율적입니다. 

DFS를 사용하게 되면 모든 조합을 리스트에 저장하지 않으므로 메모리 사용량이 줄어들어 메모리 효율성이 좋습니다. 또한, "word"를 찾는 즉시 종료하므로 불필요한 계산을 피할 수 있어 시간 효율성도 더 좋게 나타납니다. 

실제로 product으로 제출했을 때보다 DFS를 이용했을 때 시간 효율성 측면에서 많게는 2배 넘게도 차이가 나는 것을 볼 수 있습니다.  

 

오늘의 회고 

배운 알고리즘을 잘 이용하자..! 

 

 

 

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL