내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
문서 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
Problem Solving
»
문제
»
프로그래머스
»
모음 사전
ps:problems:programmers:84512
이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== 모음 사전 ====== ===== 풀이 ===== * 무식한 방법은 모든 단어를 다 만들어 놓고서 그 중에서 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)을 적용해서 쓰면 아래처럼 한줄에 코딩하는 것도 가능하다 * <dkpr py> def solution(word): return sum(1 + 'AEIOU'.index(ch) * (5**(5 - i) - 1) // 4 for i, ch in enumerate(word)) </dkpr> ===== 코드 ===== ==== 코드 1 - 모든 단어를 만들어서 위치를 찾기 ==== <dkpr py> """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)) </dkpr> ==== 코드 2 - 수식으로 계산 ==== <dkpr py> """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 </dkpr> {{tag>프로그래머스 ps:problems:programmers:Level_2}}
ps/problems/programmers/84512.txt
· 마지막으로 수정됨: 2021/08/30 15:21 저자
teferi
문서 도구
문서 보기
역링크
Fold/unfold all
맨 위로