[Level 2] 모음사전

 문제 

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

프로그래머스

 사용 언어 

Python3

 풀이 과정 

코딩 테스트 시즌이다 보니 자주 시험 보는 프로그래머스에 익숙해지려고 오랜만의 프로그래머스 문제를 셀렉(?)했다.

어떤 알고리즘을 쓸까 좀 고민은 했지만 첫 번째 제출에 통과!

 

근데 1점밖에 안 준 걸 보면 효율이 개똥인가보다. 내 생각에도 그럴 것 같은데... 문제는 이 부분이다.

# 백트래킹
def backtracking(word, tmp_word):
    global num, answer
    # print(tmp_word, num)
    if tmp_word == word:
        answer = num
        return
    if len(tmp_word) == 5:
        return

    for w in word_list:
        num += 1
        tmp_word.append(w)
        backtracking(word, tmp_word)
        tmp_word.pop()

이게 만약 백준 문제였다면 if tmp_word == word 조건을 충족했을 때 num을 출력하고 exit()으로 전체 함수를 끝내버리면 된다. 그러나 이건 프로그래머스 문제이고... 프로그래머스는 답을 출력이 아니라 return하는 형식이다.

 

그래서 return num을 하고 그걸 main 함수에서 answer 변수로 받아 바로 return하려고 했는데, 백트래킹 특성상 재귀가 계속 돌기 때문에 num은 중간에 공중분해되고 함수가 계속 돈다 ㅎㅎ 이 부분을 어떻게 해결해야 하지? 생각했는데 바로 이 포스팅을 쓰며 해결 방법이 생각났다. 재귀라서 return값이 공중분해 되는 거면 그 때에 변수로 받아서 계속 재귀를 수행할 지 안 할지 결정하면 되겠구나?! 그래서 생각난대로 고쳤더니 진짜 답까지만 찾고 끝냈다.

 

아래가 처음 제출한 코드에 대한 시간인데 답을 찾고 나서도 완전 탐색을 끝까지 수행하기 때문에 시간이 좀 걸린다.

 

그리고 답을 찾았으면 탈출하도록 변경한 코드는 다음과 같다. 확실히 앞에 있는 문자일수록 빠르게 끝날테니까 케이스에 따라 더 빨라진 게 보인다.

 

사실 U로 시작해도 A부터 완전탐색하는게 마음에 안들어서 U의 경우 A , E, I, O로 시작하는 625 * 4 경우의 수만이라도 빼고 시작하고 싶었는데 그렇게 하면 backtracking 구현 부분을 어떻게 해야 할지 헷갈려서 못 시도했다. 이 포스팅을 마치고 다시 시도해봐야겠다.

 

 제출 답안 

# 사전에 A E I O U 만 사용하여 길이 5 이하의 모든 단어가 수록되어 있음
# 사전 특성상 알파벳 순으로 정렬되어 있음

# 백트래킹
def backtracking(word, tmp_word):
    global num, answer
    # print(tmp_word, num)
    if tmp_word == word:
        return num
    if len(tmp_word) == 5:
        return

    for w in word_list:
        num += 1
        tmp_word.append(w)
        answer = backtracking(word, tmp_word)
        if answer:
            return answer
        tmp_word.pop()
    
word_list = ["A", "E", "I", "O", "U"]
num = 0
answer = ''

def solution(word):
    tmp_word = []
    backtracking(list(word), tmp_word)
    
    return answer

 

 다른 사람 코드 

1. product로 모든 경우의 수 생성 후 찾기

from itertools import product

solution = lambda word: sorted(["".join(c) for i in range(5) for c in product("AEIOU", repeat=i+1)]).index(word) + 1

➡ 제일 처음에 내가 생각했던 방식이다. product의 repeat을 이용하면 중복순열을 구현할 수 있는데 repeat의 값을 1, 2, 3, 4, 5로 반복하면 문제에서 말하는 사전에 들어갈 모든 단어를 만들 수 있다. 게다가 itertools들은 리스트 순서대로 값을 생성하기 때문에 index로 word를 찾으면 그게 바로 답이 된다.

 

2. 직접 경우의 수 계산하기

def solution(word):
    answer = 0
    for i, n in enumerate(word):
        answer += (5 ** (5 - i) - 1) / (5 - 1) * "AEIOU".index(n) + 1
    return answer

➡ 그 다음으로 내가 생각했던 방식이다. 중학교 때 배운 중복 순열의 개수 구하는 방법을 생각했는데, 그렇게 예제들을 내가 직접 계산해보니 예제 답과 다르고 머리 아파서 넘겼다. 사실 시간으로 따지면 이 방법이 제일 빠를 것 같아 구현하고 싶었는데, 이걸 포기해서 backtracking 방법 사용 시 625(5의 4제곱) * n개라도 빼보려고 한거였다..ㅎ

 

내가 직접 계산했을 때 틀렸던 이유중에 하나는 625 + 125 + 25... 이렇게 자리별로 나올 수 있는 경우의 수를 직접 더하려다보니 헷갈렸던 것 같은데, 그게 결국 5씩 곱해지는 등비수열이기 때문에 등비수열의 합공식을 이용하면 된다고 한다.

 

---

어쨌든 프로그래머스 상위에 올라와있는 방법 두 가지를 모두 "생각은 했다"는게 포인트 아닐까? (후훗 많이 발전했군) 2번은 구현하다가 포기했지만 1번은 구현할 수 있었는데 그것보다 백트래킹이 더 빠를 것 같아서 틀었다. 그리고 궁금해서 돌려보니 실제로도 백트래킹 방식이 쫌 더 빨랐다. 그런데 구현하는데 시간이 좀 걸린 것에 비해 큰 차이가 아니기 때문에 코딩테스트에 완전탐색 문제가 나오면 빠르게 itertools 라이브러리로 구현하는 게 나을 것 같다는 생각이 든다.