사용자 도구

사이트 도구


ps:problems:programmers:84512

모음 사전

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호84512
문제명모음 사전
레벨Level 2
분류

애드혹

시간복잡도O(n)
인풋사이즈n<=5
사용한 언어Python
해결날짜2021/08/30

풀이

  • 무식한 방법은 모든 단어를 다 만들어 놓고서 그 중에서 word의 위치를 찾는 것이다. 단어의 갯수는 5^5 개밖에 안되므로, 단어를 전부 생성하고, word 를 찾는것 모두 O(5*5^5)으로 처리된다.
  • 제대로 된 풀이는, 길이 n이하의 단어의 갯수, count[n]을 수식으로 계산해두는 것이다. 그 뒤, word의 첫글자가 'I'라면, 'A'또는 'E'로 시작하는 단어들은 모두 word보다 앞에 있다는 것을 알수 있다. 'A' 또는 'E'로 시작하는 단어의 갯수는 2 * count[4]이다. 마찬가지로 word의 두번째 글자가 'E'라면, 'IA'로 시작하는 단어들은 모두 word보다 앞에 있다. 이러한 단어의 갯수는 count[3]이다. 이런식으로 word보다 앞에 올수 있는 모든 단어의 갯수를 O(|word|)에 계산할수 있다.
  • count[n]은 5^0 + 5^1 + … + 5^n 이다. 코드에서는 이 식대로 계산해서 코드를 만들었지만, 등비수열의 합 공식인 (5^n - 1)/(5-1)을 적용해서 쓰면 아래처럼 한줄에 코딩하는 것도 가능하다
    • def solution(word):
          return sum(1 + 'AEIOU'.index(ch) * (5**(5 - i) - 1) // 4 for i, ch in enumerate(word))

코드

코드 1 - 모든 단어를 만들어서 위치를 찾기

"""Solution code for "Programmers 84512. 모음 사전".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/84512
- Solution link: http://www.teferi.net/ps/problems/programmers/84512
"""


import bisect
import itertools

def solution(word):
    dic = []
    for i in range(1, 6):
        dic.extend(itertools.product('AEIOU', repeat=i))
    return bisect.bisect(sorted(dic), tuple(word))

코드 2 - 수식으로 계산

"""Solution code for "Programmers 84512. 모음 사전".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/84512
- Solution link: http://www.teferi.net/ps/problems/programmers/84512
"""


def solution(word):
    v = 0
    count = [v := v + 5**i for i in range(5)]
    pos = sum(1 + 'AEIOU'.index(ch) * c for ch, c in zip(word, reversed(count)))
    return pos

토론

댓글을 입력하세요:
G L R U U
 
ps/problems/programmers/84512.txt · 마지막으로 수정됨: 2021/08/30 15:21 저자 teferi