99클럽 코테 스터디 7일차 TIL: 브루트포스

오늘의 문제 | 프로그래머스: 모음사전

처음 접근한 방식은 단순한 브루트포스로 하기로 했다. 모음 개수도 적고 경우의 수도 그리 많지 않을거 같아서 생각보다 할만해 보였다.

아이디어: 어떻게 모든 경우의 수를 알아내야 할까

생각해보니 이걸 어떻게 경우의 수를 다 찾아내야 할지가 고민된다. 처음에 생각했던건 길이가 5개라는 보장이 없기 때문에 공백 문자를 붙이는 방식을 할려 했는데 생각보다 중복이 많아질거 같아서 안되겠다.

그 다음으로 생각나는건 DP 방식으로 하나씩 원소를 추가하는 것이다. 생각보다 배열의 길이가 많이 길어지지는 않을테니까 라는 생각이 드니 모든 경우의 수만 두고 나중에 정렬하는 방식을 차용하는 것이다.

이 모든 경우의 수를 계속해서 불러내기 위해서 재귀함수를 활용하기로 했다. 다만 걱정되는건 문자열이기에 문자열 덧셈일 경우 약간은 시간이 들 수 있다는 것이다. 하지만 확실히 숫자가 크지 않아서 그런지 한번에 풀 수 있었다.

# 정답 코드
import sys

arr=[0]
for i in 'AEIOU':
    arr.append(i)
    for j in 'AEIOU':
        arr.append(i+j)
        for k in 'AEIOU':
            arr.append(i+j+k)
            for l in 'AEIOU':
                arr.append(i+j+k+l)
                for m in 'AEIOU':
                    arr.append(i+j+k+l+m)

def solution(word):
    return arr.index(word)

아무래도 이 코드의 핵심은 for문을 어떻게 순회하면서 배열을 채우나에 있는 듯하다. for문을 바로 돌리지 않고 중간중간에 배열에 넣어줬기에 별다른 코드 없이 가능한 것으로 보인다.

오늘의 회고

오늘의 알고리즘은 조금 쉬운 편이었다. 다만 왜 완전탐색 또한 알고리즘으로 분류되는지 알 수 있던 시간이라 생각한다. 어떻게 탐색을 돌리느냐가 시간이나 코드에 지대한 영향을 끼치기에 꽤나 어려울 수도 있다고 생각한다.